Создание всех возможных значений массива фиксированного размера
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])
редактировать:Кроме того, постарайтесь не использовать слишком много функций libc, потому что я буду конвертировать их в автономный загрузчик размером всего 512 байт.
Я знаю, что знаю, как это сделать, но хоть убей, я просто не могу заставить алгоритм работать у себя в голове!
Решение
Ваш вопрос страдает от странной терминологической путаницы.Из того, что вы описываете, видно, что вы хотите сгенерировать все возможные 10 кортежей беззнаковых 8-битных значений.Это не «перестановки» и все это не имеет никакого отношения к порождению перестановок.
Код, генерирующий все возможные 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 system V).Я просто пишу это здесь без тестирования, поэтому вполне возможно, что там есть ошибки.Тем не менее, основные операции кода должны быть полностью ясны.
Вместо того, чтобы работать с 80-битным буфером в памяти, я просто перебираю все возможности разделения 80-битного поля на два 64-битных регистра.Ваша процедура, проверяющая ваши условия, может сохранять их в памяти и обращаться к этой памяти как 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, глава 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);
}
пример взят из связь в котором есть другие подходы.Теория, лежащая в основе этого, довольно проста.если вам нужно, я могу подробнее объяснить алгоритм, но он вполне понятен.
Посмотри на этот алгоритм для создания комбинаций N из M предметов.Для комбинаций 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');
}
}
************************/
Ответ на этот пост также может вам помочь Алгоритм возврата всех комбинаций из k элементов из n
Если бы вы работали на 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);
