创建一个固定大小的数组的每一个可能的值
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个字节。
我知道，我知道如何做到这一点，但对我的生活我不能使算法的工作在我头上！
解决方案
您怀疑从一个奇怪的术语查询股价受到影响。从你的描述，似乎要产生8位无符号值的所有可能的10元组。这些都不是“置换”而这一切无关与发电排列。
这产生uint8_t值的所有可能的10元组的代码很容易想出。例如，下面的简单代码将执行它
#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);
}
的例子是从其中存在其他方法链接服用。其背后的原理是很简单的..如果你需要我可以进一步解释算法，但它是相当自我explainatory。
看一看该算法用于产生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);
