Création toutes les valeurs possibles d'un tableau de taille fixe
https://stackoverflow.com/questions/2003248
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je suis en train de faire quelque chose de très élémentaire qui permet de faire défiler toutes les permutations possibles d'un tableau.
Vraiment cela est fait dans l'assemblage, mais je vais l'expliquer en C.
En gros, disons que nous avons un uint8_t *data=malloc(10); tableau
Je veux créer un algorithme qui permet d'imprimer toutes les combinaisons possibles des octets dans le data tableau.
Oui, je sais que ce sera lent (et il y a beaucoup de valeurs), et je ne demande pas vraiment une version optimisée complexe .. Je cherche juste quelque chose que je peux courir sur mon repars ordinateur comme genre de chose de type force brute pour trouver certaines valeurs qui obéissent à certaines conditions ..
(note, dis-je, car la permutation [0,1,2] ne doit pas être compté le même que [2,1,0])
modifier: Aussi, essayez de ne pas utiliser trop de fonctions libc parce que je convertira à un bootloader autoportant avec seulement 512 octets.
Je sais que je sais comment faire cela, mais pour la vie de moi je ne peux pas faire fonctionner l'algorithme dans ma tête!
La solution
Votre question souffre d'une étrange mixup terminological. D'après ce que vous décrivez, il semble que vous voulez générer les 10 triplets possibles des valeurs 8 bits non signés. Ce ne sont pas « permutations » et tout cela n'a rien à voir avec les permutations de production.
Le code qui génère les 10 triplets possibles des valeurs de uint8_t est facile à trouver. Par exemple, le simple code suivant fera
#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);
Ceci est rien d'autre qu'un accroissement cyclique d'un nombre peu endian 80 bits.
Bien sûr, comme d'autres déjà noté, la quantité de temps cela va prendre fait la chose absolument inutile de tout point de vue pratique.
Autres conseils
Eh bien, tout cela est un exercice futile (voir mon commentaire attaché à la question), mais là, vous allez quand même (x86_64 AT & T assemblage de style, assume les conventions d'appel système V AMD). J'écris tout cela ici, sans essais, il est donc tout à fait possible qu'il a des bugs. Néanmoins, le fonctionnement de base du code doit être tout à fait clair.
Au lieu de fonctionner sur un tampon de 80 bits en mémoire, je suis tout simplement en cours d'exécution à travers toutes les possibilités d'une répartition sur le terrain 80 bits sur deux registres 64 bits. Votre routine qui vérifie vos conditions peuvent les stocker dans la mémoire et accéder à cette mémoire uint8_t si vous voulez vraiment.
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
Je suggère que vous avez lu,
Donald Knuth. L'art de la programmation informatique, Volume 4, Fascicule 2:. Génération tuples et Permutations
Il y a une approche récursive classique au problème qui est similaire à ce qui suit:
#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);
}
exemple est tiré de lien dans lequel il existe d'autres approches. La théorie sous-jacente est assez simple .. si vous avez besoin, je peux expliquer plus en détail l'algorithme, mais il est tout à fait auto-explainatory.
Jetez un oeil à cette algorithme pour générer des combinaisons de N sur des éléments M . Pour les combinaisons de N choisissent N, il suffit d'utiliser 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');
}
}
************************/
La réponse à ce poste peut également vous aider à algorithme pour revenir toutes les combinaisons d'éléments k de n
Si vous travaillez en 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;
}
Si vous 3 d'entrée, il sorties
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Voir permutation suivante: Lorsque C ++ obtient droit comment fonctionne std::next_permutation
Traduire ce à C ordinaire,
#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;
}
Si la question ne demande pas de permutations d'un tableau existant, mais plutôt générer tout le contenu du tableau possibles, cela est tout à fait beaucoup plus facile. (Il y a aussi beaucoup plus de combinaisons.)
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);
