Criação de todos os valores possíveis de uma matriz de tamanho fixo
https://stackoverflow.com/questions/2003248
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estou tentando fazer alguma coisa muito elementar que irá percorrer todas as permutações possíveis de uma matriz.
Realmente isso está sendo feito em conjunto, mas eu vou explicar isso em C.
Basicamente, digamos que temos um uint8_t *data=malloc(10); array
Eu quero criar um algoritmo que irá imprimir todas as combinações possíveis dos bytes no data matriz.
Sim, eu sei que vai ser lenta (e há muitos valores), e eu não estou pedindo realmente uma versão complexa otimizado .. Eu só estou procurando algo que eu possa deixar em execução no meu computador como um tipo de tipo de força bruta coisa para encontrar certos valores que obedecer a certas condições ..
(note, eu digo permutação porque [0,1,2] não deve ser contado o mesmo que [2,1,0])
edit: Além disso, tente não usar muitas funções libc porque eu vou ser converter isso para um bootloader independente com apenas 512 bytes.
Eu sei que eu sei como fazer isso, mas para a vida de mim eu não posso fazer o trabalho de algoritmo em minha cabeça!
Solução
Você pergunta sofre de uma confusão terminológica estranho. Do que você descreve parece que você deseja gerar todos os possíveis 10-tuplas de valores de 8 bits sem sinal. Estes não são "permutações" e tudo isso nada tem a ver com a geração de permutações.
O código que gera todos os possíveis 10-tuplas de valores uint8_t é fácil chegar a. Por exemplo, o seguinte código simples irá fazê-lo
#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);
Este é nada mais do que apenas um incremento cíclica de um número pouco endian 80-bit.
Claro que, como outros já observou, a quantidade de tempo isso vai levar torna a coisa toda absolutamente inútil a partir de qualquer ponto de vista prático.
Outras dicas
Bem, a coisa toda é um exercício fútil (ver o meu comentário anexado à pergunta), mas aqui vai de qualquer maneira (x86_64 AT & T estilo de montagem, assume o sistema AMD V convenções de chamada). Eu só estou escrevendo isso aqui sem testar, por isso é inteiramente possível que ele tem bugs. No entanto, a operação básica do código deve ser completamente claro.
Em vez de operar em um buffer de 80-bit na memória, estou simplesmente executando através de todas as possibilidades de uma fração de campo de 80 bits em dois registradores de 64 bits. Sua rotina que verifica suas condições pode armazená-los para a memória e acesso que a memória como uint8_t se você realmente quer.
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
Gostaria de sugerir que você lê,
Donald Knuth. The Art of Computer Programming, Volume 4, Fascicle. 2: Generating todas as tuplas e permutações
Há uma abordagem recursiva clássico para o problema que é semelhante ao seguinte:
#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);
}
exemplo é retirado ligação em que existem outras abordagens. A teoria por trás disso é muito simples .. se precisar eu posso explicar ainda mais o algoritmo, mas é bastante auto-explainatory.
Tenha um olhar em este algoritmo para gerar combinações de N fora do M itens . Para combinações de N escolher N, basta usar 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');
}
}
************************/
A resposta a este post também pode ajudá-lo a algoritmo para retornar todas as combinações de elementos de k a partir de n
Se você estava trabalhando em 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;
}
Se você 3 entrada, ele gera
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Consulte Próxima permutação:. Quando C ++ recebe-lo direita para saber como obras std::next_permutation
Traduzindo isso para C simples,
#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;
}
Se a questão não está pedindo permutações de uma matriz existente, mas sim gerar todo o conteúdo de matriz possíveis, este é bastante mais fácil. (Também há um monte mais combinações.)
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);
