如何从一组k个元素中生成长度为n的所有排列 [英] How to generate all permutations of lenght n from a set of k elements
问题描述
例如,我将元素 [1,2,3,4,5]
设置为 k = 5
,我希望所有长度为 n的排列= 2
.
For example I have this set k=5
of elements [1,2,3,4,5]
and I want all permutations of length n=2
.
1,2
1,3
1,4
1,5
2,1
etc etc.
问题是我不能使用STL,外部数学库等.
Thing is i can't use STL, external math libraries etc.
我已经在这个问题上坐了大约3天了,我要疯了.我尝试的是使用Heap算法生成所有元素的所有排列,然后在所有k个排列的前n个数字中包含n个元素的所有排列,我可以截断并删除重复项,但是复杂度是太高了(n!)
I've been sitting on this problem for about 3 days now and im about to go crazy. What i tried is generating all permutations of all the elements using Heap's algorithm, and then all the permutations of n elements where contained in the first n numbers of all k-permutations and i could just truncate and delete duplicates, but then the complexity is way too high(n!)
我知道这个问题有一个很好的解决方案,因为我已经看到额外的模块/库可以解决有关置换字符串的问题
I know the problem has a good solution as I've seen this being done with extra modules/libraries in questions about permutating strings
更多信息:我只需要用它就可以强行解决不平衡的分配问题,而当我大声强力"解决问题时,匈牙利算法似乎太长了.我的方法没有接近允许的执行时间,因为当我有一个大小为8x3的数组时,我的算法需要8!比较绝对可以将其优化为小得多的数量.
extra info : I only need this to brute force an unbalanced assignment problem, and Hungarian algorithm seems way too long when i'm aloud to "brute-force" the problem. My approach didn't come close to the allowed execution time because when i have an array of for example size 8x3, my algorithm needs 8! comparisons when it definitely could be optimized to a much smaller number.
这也是我在CS历经3年后在这里的第一篇文章,我像一百万次一样狂暴地放弃了这个问题,所以我承认失败了,并决定向您寻求帮助:
Also its my first post here after 3 years of CS, i rage-quit this problem like a million times so i admitted defeat and decided ask you stackoverflow gods for help :>
推荐答案
我认为您可以分两个步骤进行操作,首先,从一组n中生成k个元素的组合,然后打印每个组合的排列.我测试了这段代码并正常工作:
I think you can do it in two steps, first, generate combination of k elements out of a set of n, then print permutation of each combination. I tested this code and works fine:
#include <iostream>
using namespace std;
void printArr(int a[], int n, bool newline = true) {
for (int i=0; i<n; i++) {
if (i > 0) cout << ",";
cout << a[i];
}
if (newline) cout << endl;
}
// Generating permutation using Heap Algorithm
void heapPermutation(int a[], int n, int size) {
// if size becomes 1 then prints the obtained permutation
if (size == 1) {
printArr(a, n);
return;
}
for (int i=0; i<size; i++) {
heapPermutation(a, n, size-1);
// if size is odd, swap first and last element, otherwise swap ith and last element
swap(a[size%2 == 1 ? 0 : i], a[size-1]);
}
}
// Generating permutation using Heap Algorithm
void heapKPermutation(int a[], int n, int k, int size) {
// if size becomes 1 then prints the obtained permutation
if (size == n - k + 1) {
printArr(a + n - k, k);
return;
}
for (int i=0; i<size; i++) {
heapKPermutation(a, n, k, size-1);
// if size is odd, swap first and last element, otherwise swap ith and last element
swap(a[size%2 == 1 ? 0 : i], a[size-1]);
}
}
void doKCombination(int a[], int n, int p[], int k, int size, int start) {
int picked[size + 1];
for (int i = 0; i < size; ++i) picked[i] = p[i];
if (size == k) {
// We got a valid combination, use the heap permutation algorithm to generate all permutations out of it.
heapPermutation(p, k, k);
} else {
if (start < n) {
doKCombination(a, n, picked, k, size, start + 1);
picked[size] = a[start];
doKCombination(a, n, picked, k, size + 1, start + 1);
}
}
}
// Generate combination of k elements out of a set of n
void kCombination(int a[], int n, int k) {
doKCombination(a, n, nullptr, k, 0, 0);
}
int main()
{
int a[] = {1, 2, 3, 4, 5};
cout << "n=1, k=1, a=";
printArr(a, 1);
kCombination(a, 1, 1);
cout << "n=2, k=1, a=";
printArr(a, 2);
kCombination(a, 2, 1);
cout << "n=3, k=2, a=";
printArr(a, 3);
kCombination(a, 3, 2);
cout << "n=5, k=2, a=";
printArr(a, 5);
kCombination(a, 5, 2);
return 0;
}
结果是:
n=1, k=1, a=1
1
n=2, k=1, a=1,2
2
1
n=3, k=2, a=1,2,3
2,3
3,2
1,3
3,1
1,2
2,1
n=5, k=2, a=1,2,3,4,5
4,5
5,4
3,5
5,3
3,4
4,3
2,5
5,2
2,4
4,2
2,3
3,2
1,5
5,1
1,4
4,1
1,3
3,1
1,2
2,1
这篇关于如何从一组k个元素中生成长度为n的所有排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!