我基本上需要将以下Python itertools
命令的等效结果转换为C:
a = itertools.permutations(range(4),2))
目前我的过程首先涉及从10个元素中“选择”5个元素,然后为这些5个元素生成排列,如此处所示 here。
这种方法的问题在于输出顺序。我需要它是(a),而我得到的是(b),如下所示。
a = itertools.permutations(range(4),2)
for i in a:
print(i)
(0, 1)
(0, 2)
(0, 3)
(1, 0)
(1, 2)
(1, 3)
(2, 0)
(2, 1)
(2, 3)
(3, 0)
(3, 1)
(3, 2)
b = itertools.combinations(range(4),2)
for i in b:
c = itertools.permutations(i)
for j in c:
print(j)
(0, 1)
(1, 0)
(0, 2)
(2, 0)
(0, 3)
(3, 0)
(1, 2)
(2, 1)
(1, 3)
(3, 1)
(2, 3)
(3, 2)
我正在使用的另一种方法如下:
void perm(int n, int k)
{
bool valid = true;
int h = 0, i = 0, j = 0, limit = 1;
int id = 0;
int perm[10] = { 0,0,0,0,0,0,0,0,0,0 };
for (i = 0; i < k; i++)
limit *= n;
for (i = 0; i < limit; i++)
{
id = i;
valid = true;
for (j = 0; j < k; j++)
{
perms[j] = id % n;
id /= n;
for (h = j - 1; h >= 0; h--)
if (perms[j] == perms[h])
{
valid = false; break;
}
if (!valid) break;
}
if (valid)
{
for (h = k - 1; h > 0; h--)
printf("%d,", perms[h]);
printf("%d\n", perms[h]);
count++;
}
}
}
由于内存限制,我无法无限制地存储排列。性能需要比上面的算法更好,因为当 n
为50且 k
为10时,我最终会遍历更多无效组合(60+%)。
我知道 Heap's algorithm 可以原地生成排列,但它仍然是针对整个数组而不是像我需要的 k of n。
问题:
- 是否有比迭代 n^k 次更好的方法?
- 我能否创建一个惰性迭代器,给定当前排列即可移至下一个排列?
编辑:这不是 std::next_permutation 实现的重复,因为它将排列整个输入范围。 我已经清楚地说明了我需要 n 中长度为 k 的所有排列。如果我的范围为 10,我希望所有长度为 k(例如 5)的排列,std::next_permutation 适用于长度或排列与输入范围的长度相同的情况。
更新: 这是一个丑陋的递归 NextPerm 解决方案,大约比我的旧解决方案快4倍,并提供类似 Python 的惰性迭代器的增量 nextPerm。
int nextPerm(int perm[], int k, int n)
{
bool invalid = true;
int subject,i;
if (k == 1)
{
if (perm[0] == n - 1)
return 0;
else { perm[0]=perm[0]+1; return 1; }
}
subject = perm[k - 1]+1;
while (invalid)
{
if (subject == n)
{
subject = 0;
if (!nextPerm(perm, k - 1, n))
return 0;
}
for (i = 0; i < k-1; i++)
{
if (perm[i] != subject)
invalid = false;
else
{
invalid = true;subject++; break;
}
}
}
perm[k - 1] = subject;
return 1;
}
int main()
{
int a, k =3 ,n = 10;
int perm2[3] = { 0,1,2}; //starting permutation
unsigned long long count = 0;
int depth = 0;
do
{
for (a = 0; a < k - 1; a++)
printf("%d,", perm2[a]);
printf("%d\n", perm2[k - 1]);
count++;
}
while (nextPerm(perm2,k,n));
printf("\n%llu", count);
getchar();
return 0;
}
std::next_permutation
的代码之外,这个算法 就是你要找的。该算法是回答问题 在 C++ 中生成 N 选 K 排列 的答案。关键是在每次排列后反转从k+1
到n
的元素,以避免重复排列。 - Emil