例如，我具有元素k=5的这个集合[1,2,3,4,5]，并且我希望长度为n=2的所有排列。
1,2
1,3
1,4
1,5
2,1
etc etc.
我无法使用STL，外部数学库等。
我已经在这个问题上坐了大约3天了，我快要疯了。我尝试的是使用Heap算法生成所有元素的所有排列，然后在所有k个排列的前n个数字中包含n个元素的所有排列，我可以截断和删除重复项，但是复杂度是太高（n！）
[我知道这个问题有一个很好的解决方案，因为我已经看到了有关置换字符串的问题，这是通过额外的模块/库完成的
额外信息：我只需要使用它就可以强行解决不平衡的分配问题，而当我大声“强力”解决问题时，匈牙利算法似乎太长了。我的方法没有接近允许的执行时间，因为当我有一个大小为8x3的数组时，我的算法需要8！比较，肯定可以将其优化到更小的数量。
这也是我在CS历经3年后在这里的第一篇文章，我像一百万次一样狂暴地放弃了这个问题，所以我承认失败了，并决定向您请教stackoverflow众神寻求帮助：>
实际上，您可以将k作为第一个值。
然后，选择了第一个值后，问题是使用n-1和k-1参数生成所有排列。
这导致一个相当简单的递归实现。可能会有更快的方法。但是，它显然比您的算法快。
#include <iostream>
#include <algorithm>
bool Pnk (int n, int k, int *a, int iter, int offset) {
if (n == 0) {
return false;
}
bool check = true;
int index = 0;
std::swap (a[iter], a[iter+offset]);
while (check) {
if (n-1 == 0) {
for (int i = 0; i <= iter; ++i) {
std::cout << a[i] << " ";
}
std::cout << "\n";
}
check = Pnk (n-1, k-1, a, iter + 1, index);
index++;
}
std::swap (a[iter], a[iter+offset]);
return offset != k-1;
}
void Pnk0 (int n, int k, int *a) {
int offset = 0;
while (Pnk (n, k, a, 0, offset)) {
offset++;
}
}
int main () {
int length = 3;
const int size = 4;
int a[size] = {1, 2, 3, 4};
Pnk0 (length, size, a);
}
我认为您可以分两个步骤进行操作，首先，从一组n中生成k个元素的组合，然后打印每个组合的排列。我测试了此代码，并正常工作：
#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
如果您不关心按字典顺序排列的输出，这是一个相当简单的实现。
using namespace std;
void perm(int* a, int n, int k, int i)
{
if(i == 0)
{
for(int j=n; j<n+k; j++) cout << a[j] << " ";
cout << endl;
return;
}
for(int j=0; j<n; j++)
{
swap(a[j], a[n-1]);
perm(a, n-1, k, i-1);
swap(a[j], a[n-1]);
}
}
测试：
int n = 4, k = 2;
int a[] = {1,2,3,4};
perm(a, n, k, k);
输出：
4 1
2 1
3 1
1 2
4 2
3 2
1 3
2 3
4 3
1 4
2 4
3 4
我不知道n是否总是2，但是如果您不介意性能，这是一些“”“”“”“代码：
#include <iostream>
#include <tuple>
#include <vector>
std::vector<std::tuple<int, int> >
get_tuples_from_vector (const std::vector<int> elements)
{
std::vector<std::tuple<int, int> > tuples;
for (int i = 0; i < elements.size(); ++i)
{
for (int j = i + 1; j < elements.size(); ++j)
{
tuples.push_back({elements[i], elements[j]});
}
}
return tuples;
}
std::vector<std::tuple<int, int> >
generate_permutations (const std::vector<int>& elements)
{
if (elements.size() == 0 || elements.size() < 2)
{
return {};
}
std::vector<std::tuple<int, int> > tuples
{
get_tuples_from_vector(elements)
};
std::vector<std::tuple<int, int> > permutations;
for (const auto& tuple: tuples)
{
permutations.push_back(
{ std::get<0>(tuple), std::get<1>(tuple) }
);
permutations.push_back(
{ std::get<1>(tuple), std::get<0>(tuple) }
);
}
return permutations;
}
void print_vector(std::vector<std::tuple<int, int> > elements)
{
for (const auto& element: elements)
{
std::cout << "[ "
<< std::get<0>(element)
<< ", " << std::get<1>(element)
<< "]\n";
}
std::cout << std::endl;
}
int main(int argc, char const *argv[])
{
print_vector(generate_permutations({1, 2, 3, 4, 5}));
}