고정 크기 배열의 모든 가능한 값을 만듭니다
https://stackoverflow.com/questions/2003248
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 배열의 가능한 모든 순열을 순환 할 매우 기본적인 것을 만들려고 노력하고 있습니다.
실제로 이것은 조립에서 수행되고 있지만 C로 설명하겠습니다.
기본적으로 배열이 있다고 말합니다 uint8_t *data=malloc(10);
배열에서 바이트의 모든 가능한 조합을 인쇄 할 알고리즘을 만들고 싶습니다. data.
예, 나는 그것이 느릴 것임을 알고 있습니다 (그리고 많은 값이 있습니다). 나는 복잡한 최적화 버전을 요구하지 않습니다. 나는 단지 컴퓨터에서 일종의 무차별으로 달리는 것을 찾고 있습니다. -특정 조건에 순종하는 특정 값을 찾기위한 유형의 요소 ..
([0,1,2]가 [2,1,0]과 동일하게 계산되어서는 안되기 때문에 순열이라고 말합니다.
편집 : 또한 512 바이트 만있는 독립형 부트 로더로 변환하기 때문에 너무 많은 LIBC 기능을 사용하지 마십시오.
나는 이것을하는 방법을 알고 있지만 내 삶을 위해 알고리즘이 내 머리에 작동하게 할 수는 없습니다!
해결책
당신은 이상한 용어 혼합으로 고통받는 질문입니다. 당신이 묘사 한 바에 따르면 서명되지 않은 8 비트 값의 가능한 모든 10 선을 생성하려는 것으로 보입니다. 이것들은 "순열"이 아니며이 모든 것은 순열을 생성하는 것과 아무 관련이 없습니다.
가능한 모든 10 타점을 생성하는 코드 uint8_t 값은 쉽게 생각해냅니다. 예를 들어 다음 간단한 코드가 수행됩니다
#define N 10u
uint8_t data[N] = { 0 };
unsigned i;
do {
/* Process the current 10-typle in `data` array */
/* in any way you want do */
/* Generate next tuple */
for (i = 0; i < N && ++data[i] == 0; ++i);
} while (i < N);
이것은 80 비트 리틀 엔디 언 숫자의 순환 단지 단지 다른 일입니다.
물론, 다른 사람들이 이미 언급했듯이, 이것이 취할 시간의 양은 모든 것을 실용적인 관점에서 절대적으로 쓸모 없게 만듭니다.
다른 팁
글쎄, 모든 것은 쓸데없는 운동입니다 (질문에 첨부 된 내 의견 참조). 그러나 여기서 당신은 어쨌든 간다 (x86_64 AT & T 스타일 어셈블리, AMD 시스템 v 호출 규칙을 가정합니다). 나는 단지 테스트없이 여기에 글을 쓰고 있으므로 버그가있을 수 있습니다. 그럼에도 불구하고 코드의 기본 작동은 완전히 명확해야합니다.
메모리에서 80 비트 버퍼에서 작동하는 대신 두 개의 64 비트 레지스터에 걸쳐 80 비트 필드 분할의 모든 가능성을 실행하고 있습니다. 조건을 점검하는 루틴은이를 메모리에 저장하고 그 메모리에 액세스 할 수 있습니다. uint8_t 당신이 정말로 원한다면.
push r12
push r13
xor r12, r12 // zero out low 64 bits of our "buffer" in register
xor r13, r13 // zero out high 16 bits of our "buffer"
loop:
// Copy the current array value into rsi:rdi and call whatever routine you're
// using to check for magic conditions. This routine's copy (in r13:r12)
// should be unaffected if you're obeying the System V calling conventions.
mov r12, rdi
mov r13, rsi
call _doSomethingWithValue
// Increment r13:r12 to get the next value. We only need to worry about r13
// if the increment of r12 wraps around to zero.
inc r12
jnz loop
inc r13
// Check for the termination condition, though you'll never hit it =)
cmp $0x10000, r13
jne loop
// We don't actually need to clean up; the apocalypse will come and there
// won't be electricity to run the computer before it reaches this point of
// the program. Nonetheless, let's be exhaustively correct.
pop r13
pop r12
나는 당신이 읽을 것을 제안합니다.
도널드 크 누스. 컴퓨터 프로그래밍 기술, 4 권, Fascicle 2 : 모든 튜플 및 순열 생성.
문제에 대한 고전적인 재귀 적 접근 방식이 다음과 유사합니다.
#include <stdio.h>
void print(const uint8_t *v, const int size)
{
if (v != 0) {
for (int i = 0; i < size; i++) {
printf("%4d", v[i] );
}
printf("\n");
}
} // print
void visit(uint8_t *Value, int N, int k)
{
static level = -1;
level = level+1; Value[k] = level;
if (level == N)
print(Value, N);
else
for (int i = 0; i < N; i++)
if (Value[i] == 0)
visit(Value, N, i);
level = level-1; Value[k] = 0;
}
main()
{
const int N = 4;
uint8_t Value[N];
for (int i = 0; i < N; i++) {
Value[i] = 0;
}
visit(Value, N, 0);
}
예제에서 가져온 것입니다 링크 다른 접근법이 있습니다. 그 뒤에있는 이론은 매우 간단합니다. 필요하다면 알고리즘을 더 설명 할 수 있지만 매우 자체 설명 적입니다.
살펴보십시오 이 알고리즘 m 항목에서 n의 조합을 생성합니다. n 선택 n의 조합의 경우 inittwiddle (n, n, p)을 사용하십시오.
int twiddle(x, y, z, p)
int *x, *y, *z, *p;
{
register int i, j, k;
j = 1;
while(p[j] <= 0)
j++;
if(p[j-1] == 0)
{
for(i = j-1; i != 1; i--)
p[i] = -1;
p[j] = 0;
*x = *z = 0;
p[1] = 1;
*y = j-1;
}
else
{
if(j > 1)
p[j-1] = 0;
do
j++;
while(p[j] > 0);
k = j-1;
i = j;
while(p[i] == 0)
p[i++] = -1;
if(p[i] == -1)
{
p[i] = p[k];
*z = p[k]-1;
*x = i-1;
*y = k-1;
p[k] = -1;
}
else
{
if(i == p[0])
return(1);
else
{
p[j] = p[i];
*z = p[i]-1;
p[i] = 0;
*x = j-1;
*y = i-1;
}
}
}
return(0);
}
void inittwiddle(m, n, p)
int m, n, *p;
{
int i;
p[0] = n+1;
for(i = 1; i != n-m+1; i++)
p[i] = 0;
while(i != n+1)
{
p[i] = i+m-n;
i++;
}
p[n+1] = -2;
if(m == 0)
p[1] = 1;
}
/************************
Here is a sample use of twiddle() and inittwiddle():
#define N 5
#define M 2
#include <stdio.h>
void main()
{
int i, x, y, z, p[N+2], b[N];
inittwiddle(M, N, p);
for(i = 0; i != N-M; i++)
{
b[i] = 0;
putchar('0');
}
while(i != N)
{
b[i++] = 1;
putchar('1');
}
putchar('\n');
while(!twiddle(&x, &y, &z, p))
{
b[x] = 1;
b[y] = 0;
for(i = 0; i != N; i++)
putchar(b[i]? '1': '0');
putchar('\n');
}
}
************************/
이 게시물에 대한 답변도 도움이 될 수 있습니다 n에서 k 요소의 모든 조합을 반환하는 알고리즘
C ++에서 일하고 있다면
#include <algorithm>
#include <iterator>
#include <iostream>
#include <numeric>
int main() {
int N;
std::cin >> N;
std::vector<int> data(N);
std::fill(data.begin(), data.end(), 1);
std::partial_sum(data.begin(), data.end(), data.begin());
do {
std::copy(data.begin(), data.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
} while (std::next_permutation(data.begin(), data.end()));
return 0;
}
입력 한 경우 3, 출력
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
보다 다음 순열 : C ++가 올바르게 얻을 때 어떻게 std::next_permutation 공장.
이것을 일반 C로 번역하고
#include <stdio.h>
#include <stdlib.h>
int main() {
int i, N, *data;
scanf("%d", &N);
data = malloc(N);
for (i = 0; i < N; i++) data[i] = i + 1;
while (1) {
int j, temp;
for (i = 0; i < N; i++) printf("%d ", data[i]);
printf("\n");
for (i = N - 1; i > 0 && data[i] < data[i - 1]; i--);
if (i <= 0) break;
for (j = N; data[i - 1] >= data[--j];);
temp = data[i - 1], data[i - 1] = data[j], data[j] = temp;
for (j = N - 1; i < j; i++, j--)
temp = data[i], data[i] = data[j], data[j] = temp;
}
return 0;
}
질문이 기존 배열의 순열을 요구하는 것이 아니라 가능한 모든 배열 내용을 생성하는 경우 훨씬 쉽습니다. (또한 더 많은 조합이 있습니다.)
memset(data, 0, N);
do {
for (i = 0; i < N; i++) printf("%d ", data[i]);
printf("\n");
for (i = 0; i < N && !++data[i++];);
} while (i < N);
