Erstellen jeden möglichen Wert von einer festen Größe Array
https://stackoverflow.com/questions/2003248
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, einige sehr elementare Sache, die radeln durch jede mögliche Permutation eines Arrays zu machen.
Wirklich diese bei der Montage durchgeführt werden, aber ich werde es in C erklären.
Im Grunde sagen wir ein Array uint8_t *data=malloc(10); haben
Ich möchte einen Algorithmus erstellen, die jede mögliche Kombination der Bytes im Array data gedruckt wird.
Ja, ich weiß, es wird langsam sein (und es gibt viele Werte), und ich bin nicht für wirklich eine komplexe optimierte Version zu fragen .. Ich bin nur die Suche nach etwas, das ich als ein auf meinem Computer laufen lassen Art von Brute-Force-Typ, was bestimmte Werte zu finden, die bestimmten Bedingungen gehorchen ..
(beachten Sie, sage ich Permutation weil [0,1,2] sollte nicht als selben gezählt werden [2,1,0])
edit: Versuchen Sie auch, nicht zu viele libc-Funktionen zu verwenden, weil ich mit nur 512 Bytes dies zu einem freistehenden Bootloader Umwandlung wird.
Ich weiß, ich weiß, wie dies zu tun, sondern für das Leben von mir kann ich einfach nicht die Algorithmus Arbeit in meinem Kopf machen!
Lösung
Sie fragen leidet an einer seltsamen terminologische mixup. Von dem, was Sie beschreiben, scheint es, dass Sie alle möglichen 10-Tupel von unsigned 8-Bit-Werte generieren möchten. Diese sind nicht „Permutationen“ und all dies hat nichts mit der Erzeugung Permutationen zu tun.
Der Code, der alle möglichen 10-Tupel von uint8_t Werte erzeugt, ist einfach zu kommen mit. Zum Beispiel wird der folgende einfache Code tut es
#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);
Das ist nichts anderes als nur eine zyklische Zunahme einer 80-Bit-Little-Endian-Nr.
Natürlich, wie andere bereits erwähnt, ist die Menge an Zeit, dies dauern wird, macht das Ganze absolut nutzlos von jedem praktischen Standpunkt aus.
Andere Tipps
Nun, das Ganze ein aussichtsloses Unterfangen ist (siehe mein Kommentar auf die Frage angebracht ist), aber hier geht man sowieso (x86_64 AT & T Stil Montag nimmt die AMD-System V Aufrufkonventionen). Ich schreibe gerade diese hier ohne Prüfung, so ist es durchaus möglich, dass es hat Fehler. Dennoch sollten die grundlegenden Funktionsweise des Codes ganz klar sein.
Statt auf einem 80-Bit-Puffer im Speicher arbeitet, ich bin einfach durch alle Möglichkeiten eines 80-Bit-Feld verteilt auf zwei 64-Bit-Register ausgeführt wird. Ihre Routine, die überprüft Ihre Bedingungen können sie in den Speicher speichern und diese Speicher als uint8_t zugreifen, wenn Sie wirklich wollen.
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
Ich würde vorschlagen, dass Sie lesen,
Donald Knuth. Die Art of Computer Programming, Band 4, Faszikel. 2: Gene Alle Tupeln und Permutationen
Es ist eine klassische rekursiven Annäherung an das Problem, die den folgend ähnelt:
#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);
}
Beispiel von Link , in denen andere Ansätze gibt. Die Theorie dahinter ist ganz einfach .. wenn du ich brauche weiter den Algorithmus erklären, aber es ist ziemlich selbsterklärend.
Hier finden Sie aktuelle diesen Algorithmus für Kombinationen von N aus M Elementen zu erzeugen . Für Kombinationen von N N wählen, benutzen Sie einfach 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');
}
}
************************/
Die Antwort auf diesen Beitrag kann Ihnen auch helfen, Algorithmus zurückzukehren alle Kombinationen von k Elementen aus n
Wenn Sie arbeiten in 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;
}
Wenn Sie den Eingang 3, es gibt
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Siehe Nächste Permutation: Wenn C ++ wird es richtig wie std::next_permutation Werke
Die Umsetzung dieses auf Ebene 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;
}
Wenn die Frage zu stellen ist nicht für Permutationen eines vorhandenen Arrays, sondern alle möglichen Array Inhalte zu erzeugen, das ist ziemlich viel einfacher. (Es gibt auch viel mehr Kombinationen.)
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);
