如何从k个元素的集合中生成长度为n的所有排列？ [英] How can I generate all permutations of length n from a set of k elements?

问题描述

例如，我有一组k=5元素[1,2,3,4,5]，我想要长度为n=2的所有排列。

1,2
1,3
1,4
1,5
2,1
etc etc. 

问题是我不能使用STL、外部数学库等。

我尝试的是用Heap的算法生成所有元素的所有排列，然后n个元素的所有排列包含在所有k个排列的前n个数中，我可以只截断并删除重复项，但这样的复杂性太高了(n！)

我知道这个问题有一个很好的解决方案，因为我在有关置换字符串的问题中看到过使用额外的模块/库来解决这个问题。

额外信息：我只需要用它来强制解决不平衡的赋值问题，而当我被允许强行解决问题时，匈牙利算法似乎太长了。我的方法没有接近允许的执行时间，因为当我有一个大小为8x3的数组时，我的算法需要8！当它肯定可以优化到一个小得多的数字时进行比较。

推荐答案

我认为可以分两步完成，首先，从一组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

这篇关于如何从k个元素的集合中生成长度为n的所有排列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！