在 C 中从 n 生成 k 排列
Generating k permutations from n in C
我基本上需要 C:
中以下 Python itertools 命令的等效结果
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 用于就地生成排列，但它再次为整个数组生成，而不是像我需要的那样生成 n 个中的第 k 个。
问题。
- 有比迭代 n^k 次更好的方法吗？
- 我可以制作一个惰性迭代器，在给定当前排列的情况下移动到下一个排列吗？
EDIT 这不是 std::next_permutation 实现的重复，因为它将置换整个输入范围。
我已经明确提到我需要 n 个排列中的 k 个。即，如果我的范围是 10，我想要长度 (k) 的所有排列，比如 5，std::next_permutation 在长度或排列与输入范围的长度相同时工作 [=19] =]
更新
这是一个丑陋的递归 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;
}
对标准排列算法进行简单修改，将产生 k-排列。
字典顺序排列（又名std::next_permutation）
在 C++ 中，k-排列可以通过使用 std::next_permutation 的简单权宜之计生成，只需在每次调用 std::next_permutation 之前反转排列的 n-k- 后缀。
它是如何工作的相当清楚：算法按顺序生成排列，因此以给定前缀开头的第一个排列具有递增顺序的剩余后缀，具有相同前缀的最后一个排列具有递减顺序的后缀.降序只是升序的倒转，所以一次调用 std::reverse 就足够了。
字典顺序next-permutation算法很简单：
从末尾向后搜索可以通过与后面的元素交换来增加的元素。
一旦找到最右边的这样的元素，找到可以与之交换的最小后续元素，并交换它们。
将新后缀按升序排序（通过反转它，因为它之前是降序排列）。
字典算法的一个优点是它可以透明地处理具有重复元素的数组。只要任何给定元素的重复次数为 O(1)，next-permutation 的摊销时间为 O(1)（每次调用），最坏情况下为 O(n)。生成 k 排列时，额外的翻转导致 next_k_permutation 的成本为 O(n-k)，如果 k 固定，则实际上是 O(n)。这仍然相当快，但不如非迭代算法快，非迭代算法可以保持状态而不是在步骤 1 中进行搜索以找出要移动的元素。
以下 C 实现等效于 std::reverse(); std::next_permutation();（除了它在反转之前交换）：
#include <stddef.h>
/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}
/* Given an array of n elements, finds the next permutation in
* lexicographical order with a different k-prefix; in effect, it
* generates all k-permutations of the array.
* It is required that the suffix be sorted in ascending order. This
* invariant will be maintained by the function.
* Before the first call, the array must be sorted in ascending order.
* Returns true unless the input is the last k-permutation.
*/
int next_k_permutation(int* elements, size_t n, size_t k) {
// Find the rightmost element which is strictly less than some element to its
// right.
int tailmax = elements[n - 1];
size_t tail = k;
while (tail && elements[tail - 1] >= tailmax)
tailmax = elements[--tail];
// If no pivot was found, the given permutation is the last one.
if (tail) {
size_t swap_in;
int pivot = elements[tail - 1];
// Find the smallest element strictly greater than the pivot, either
// by searching forward from the pivot or backwards from the end.
if (pivot >= elements[n - 1]) {
for (swap_in = tail; swap_in + 1 < k && elements[swap_in + 1] > pivot; ++swap_in) {}
} else {
for (swap_in = n - 1; swap_in > k && elements[swap_in - 1] > pivot; --swap_in) {}
}
// Swap the pivots
elements[tail - 1] = elements[swap_in];
elements[swap_in] = pivot;
// Flip the tail.
flip(elements, k, n);
flip(elements, tail, n);
}
return tail;
}
这是一个简单的驱动程序和一个示例 运行:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int intcmp(const void* a, const void* b) {
return *(int*)a < *(int*)b ? -1 :
*(int*)a > *(int*)b ? 1 :
0 ;
}
int main(int argc, char** argv) {
size_t k = (argc > 1) ? atoi(argv[1]) : 0;
if (argc < k + 2) {
fprintf(stderr, "Usage: %s K element...\n"
" where K <= number of elements\n",
argv[0]);
return 1;
}
size_t n = argc - 2;
int elements[n];
for (int i = 0; i < n; ++i) elements[i] = atoi(argv[i + 2]);
qsort(elements, n, sizeof *elements, intcmp);
do {
const char* delimiter = "";
for (size_t i = 0; i < k; ++i) {
printf("%s%2d ", delimiter, elements[i]);
delimiter = " ";
}
putchar('\n');
} while (next_k_permutation(elements, n, k));
return 0;
}
样本运行（有重复元素）：
$ ./k_next_permutation 2 7 3 4 4 5
3 4
3 5
3 7
4 3
4 4
4 5
4 7
5 3
5 4
5 7
7 3
7 4
7 5
修改堆算法
作为保持状态的算法示例，可以轻松修改 Heap 的算法以生成 k 排列。唯一的变化是，当算法向下递归到位置 n - k 时，k 后缀被报告为 k 排列，并且 (n-k) 前缀按照堆算法转换它的方式进行转换，如果它是 运行 结论：长度为奇数时前缀反转，长度为偶数时向左旋转一位。 （顺便说一下，这是关于 Heap 算法如何工作的重要提示。）
使用递归算法有点烦人，因为它实际上不允许增量排列。然而，它很容易遵循。在这里，我刚刚将一个仿函数传递给递归过程，该过程依次调用每个排列。
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}
static void rotate_left(int* elements, size_t lo, size_t hi) {
if (hi > lo) {
int tmp = elements[lo];
for (size_t i = lo + 1; i < hi; ++i) elements[i - 1] = elements[i];
elements[hi - 1] = tmp;
}
}
/* Recursive function; the main function will fill in the extra parameters */
/* Requires hi >= lo and hi >= k. Array must have size (at least) lo + k */
static bool helper(int* array, size_t lo, size_t k, size_t hi,
bool(*process)(void*, int*, size_t), void* baton) {
if (hi == lo) {
if (!process(baton, array + lo, k)) return false;
if (lo % 2)
flip(array, 0, lo);
else
rotate_left(array, 0, lo);
}
else {
for (size_t i = 0; i < hi - 1; ++i) {
if (!helper(array, lo, k, hi - 1, process, baton))
return false;
swap(array, hi % 2 ? 0 : i, hi - 1);
}
if (!helper(array, lo, k, hi - 1, process, baton))
return false;
}
return true;
}
/* Generate all k-permutations of the given array of size n.
* The process function is called with each permutation; if it returns false,
* generation of permutations is terminated.
*/
bool k_heap_permute(int* array, size_t n, size_t k,
bool(*process)(void*, int*, size_t), void* baton) {
assert(k <= n);
return helper(array, n - k, k, n, process, baton);
}
这是一个使用示例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
bool print_array(void* vf, int* elements, size_t n) {
FILE* f = vf;
const char* delim = "";
for (size_t i = 0; i < n; ++i) {
fprintf(f, "%s%2d", delim, elements[i]);
delim = " ";
}
putc('\n', f);
return true;
}
int main(int argc, char** argv) {
size_t k = (argc > 1) ? atoi(argv[1]) : 0;
if (argc < k + 2) {
fprintf(stderr, "Usage: %s K element...\n"
" where K <= number of elements\n",
argv[0]);
return 1;
}
size_t n = argc - 2;
int elements[n];
for (int i = 0; i < n; ++i)
elements[i] = atoi(argv[i + 2]);
k_heap_permute(elements, n, k, print_array, stdout);
return 0;
}
样本运行：
$ ./permut 2 1 5 9 7 3
7 3
9 3
5 3
1 3
1 5
7 5
9 5
3 5
3 9
1 9
7 9
5 9
5 7
3 7
1 7
9 7
9 1
5 1
3 1
7 1
我基本上需要 C:
中以下 Pythonitertools 命令的等效结果
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 用于就地生成排列，但它再次为整个数组生成，而不是像我需要的那样生成 n 个中的第 k 个。
问题。
- 有比迭代 n^k 次更好的方法吗？
- 我可以制作一个惰性迭代器，在给定当前排列的情况下移动到下一个排列吗？
EDIT 这不是 std::next_permutation 实现的重复，因为它将置换整个输入范围。 我已经明确提到我需要 n 个排列中的 k 个。即，如果我的范围是 10，我想要长度 (k) 的所有排列，比如 5，std::next_permutation 在长度或排列与输入范围的长度相同时工作 [=19] =]
更新 这是一个丑陋的递归 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;
}
对标准排列算法进行简单修改，将产生 k-排列。
字典顺序排列（又名std::next_permutation）
在 C++ 中，k-排列可以通过使用 std::next_permutation 的简单权宜之计生成，只需在每次调用 std::next_permutation 之前反转排列的 n-k- 后缀。
它是如何工作的相当清楚：算法按顺序生成排列，因此以给定前缀开头的第一个排列具有递增顺序的剩余后缀，具有相同前缀的最后一个排列具有递减顺序的后缀.降序只是升序的倒转，所以一次调用 std::reverse 就足够了。
字典顺序next-permutation算法很简单：
从末尾向后搜索可以通过与后面的元素交换来增加的元素。
一旦找到最右边的这样的元素，找到可以与之交换的最小后续元素，并交换它们。
将新后缀按升序排序（通过反转它，因为它之前是降序排列）。
字典算法的一个优点是它可以透明地处理具有重复元素的数组。只要任何给定元素的重复次数为 O(1)，next-permutation 的摊销时间为 O(1)（每次调用），最坏情况下为 O(n)。生成 k 排列时，额外的翻转导致 next_k_permutation 的成本为 O(n-k)，如果 k 固定，则实际上是 O(n)。这仍然相当快，但不如非迭代算法快，非迭代算法可以保持状态而不是在步骤 1 中进行搜索以找出要移动的元素。
以下 C 实现等效于 std::reverse(); std::next_permutation();（除了它在反转之前交换）：
#include <stddef.h>
/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}
/* Given an array of n elements, finds the next permutation in
* lexicographical order with a different k-prefix; in effect, it
* generates all k-permutations of the array.
* It is required that the suffix be sorted in ascending order. This
* invariant will be maintained by the function.
* Before the first call, the array must be sorted in ascending order.
* Returns true unless the input is the last k-permutation.
*/
int next_k_permutation(int* elements, size_t n, size_t k) {
// Find the rightmost element which is strictly less than some element to its
// right.
int tailmax = elements[n - 1];
size_t tail = k;
while (tail && elements[tail - 1] >= tailmax)
tailmax = elements[--tail];
// If no pivot was found, the given permutation is the last one.
if (tail) {
size_t swap_in;
int pivot = elements[tail - 1];
// Find the smallest element strictly greater than the pivot, either
// by searching forward from the pivot or backwards from the end.
if (pivot >= elements[n - 1]) {
for (swap_in = tail; swap_in + 1 < k && elements[swap_in + 1] > pivot; ++swap_in) {}
} else {
for (swap_in = n - 1; swap_in > k && elements[swap_in - 1] > pivot; --swap_in) {}
}
// Swap the pivots
elements[tail - 1] = elements[swap_in];
elements[swap_in] = pivot;
// Flip the tail.
flip(elements, k, n);
flip(elements, tail, n);
}
return tail;
}
这是一个简单的驱动程序和一个示例 运行:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int intcmp(const void* a, const void* b) {
return *(int*)a < *(int*)b ? -1 :
*(int*)a > *(int*)b ? 1 :
0 ;
}
int main(int argc, char** argv) {
size_t k = (argc > 1) ? atoi(argv[1]) : 0;
if (argc < k + 2) {
fprintf(stderr, "Usage: %s K element...\n"
" where K <= number of elements\n",
argv[0]);
return 1;
}
size_t n = argc - 2;
int elements[n];
for (int i = 0; i < n; ++i) elements[i] = atoi(argv[i + 2]);
qsort(elements, n, sizeof *elements, intcmp);
do {
const char* delimiter = "";
for (size_t i = 0; i < k; ++i) {
printf("%s%2d ", delimiter, elements[i]);
delimiter = " ";
}
putchar('\n');
} while (next_k_permutation(elements, n, k));
return 0;
}
样本运行（有重复元素）：
$ ./k_next_permutation 2 7 3 4 4 5
3 4
3 5
3 7
4 3
4 4
4 5
4 7
5 3
5 4
5 7
7 3
7 4
7 5
修改堆算法
作为保持状态的算法示例，可以轻松修改 Heap 的算法以生成 k 排列。唯一的变化是，当算法向下递归到位置 n - k 时，k 后缀被报告为 k 排列，并且 (n-k) 前缀按照堆算法转换它的方式进行转换，如果它是 运行 结论：长度为奇数时前缀反转，长度为偶数时向左旋转一位。 （顺便说一下，这是关于 Heap 算法如何工作的重要提示。）
使用递归算法有点烦人，因为它实际上不允许增量排列。然而，它很容易遵循。在这里，我刚刚将一个仿函数传递给递归过程，该过程依次调用每个排列。
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
/* Helper functions */
static void swap(int* elements, size_t a, size_t b) {
int tmp = elements[a]; elements[a] = elements[b]; elements[b] = tmp;
}
static void flip(int* elements, size_t lo, size_t hi) {
for (; lo + 1 < hi; ++lo, --hi) swap(elements, lo, hi - 1);
}
static void rotate_left(int* elements, size_t lo, size_t hi) {
if (hi > lo) {
int tmp = elements[lo];
for (size_t i = lo + 1; i < hi; ++i) elements[i - 1] = elements[i];
elements[hi - 1] = tmp;
}
}
/* Recursive function; the main function will fill in the extra parameters */
/* Requires hi >= lo and hi >= k. Array must have size (at least) lo + k */
static bool helper(int* array, size_t lo, size_t k, size_t hi,
bool(*process)(void*, int*, size_t), void* baton) {
if (hi == lo) {
if (!process(baton, array + lo, k)) return false;
if (lo % 2)
flip(array, 0, lo);
else
rotate_left(array, 0, lo);
}
else {
for (size_t i = 0; i < hi - 1; ++i) {
if (!helper(array, lo, k, hi - 1, process, baton))
return false;
swap(array, hi % 2 ? 0 : i, hi - 1);
}
if (!helper(array, lo, k, hi - 1, process, baton))
return false;
}
return true;
}
/* Generate all k-permutations of the given array of size n.
* The process function is called with each permutation; if it returns false,
* generation of permutations is terminated.
*/
bool k_heap_permute(int* array, size_t n, size_t k,
bool(*process)(void*, int*, size_t), void* baton) {
assert(k <= n);
return helper(array, n - k, k, n, process, baton);
}
这是一个使用示例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
bool print_array(void* vf, int* elements, size_t n) {
FILE* f = vf;
const char* delim = "";
for (size_t i = 0; i < n; ++i) {
fprintf(f, "%s%2d", delim, elements[i]);
delim = " ";
}
putc('\n', f);
return true;
}
int main(int argc, char** argv) {
size_t k = (argc > 1) ? atoi(argv[1]) : 0;
if (argc < k + 2) {
fprintf(stderr, "Usage: %s K element...\n"
" where K <= number of elements\n",
argv[0]);
return 1;
}
size_t n = argc - 2;
int elements[n];
for (int i = 0; i < n; ++i)
elements[i] = atoi(argv[i + 2]);
k_heap_permute(elements, n, k, print_array, stdout);
return 0;
}
样本运行：
$ ./permut 2 1 5 9 7 3
7 3
9 3
5 3
1 3
1 5
7 5
9 5
3 5
3 9
1 9
7 9
5 9
5 7
3 7
1 7
9 7
9 1
5 1
3 1
7 1