Как сгенерировать все перестановки длины n из набора k элементов

Question

Например, у меня есть этот набор k=5 элементов [1,2,3,4,5], и я хочу, чтобы все перестановки имели длину n=2.

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

Дело в том, что я не могу использовать STL, внешние математические библиотеки и т. Д. c.

Я сижу над этой проблемой уже около 3 дней, и я почти сошел с ума. Я попытался сгенерировать все перестановки всех элементов с использованием алгоритма Heap, а затем все перестановки из n элементов, содержащихся в первых n числах всех k-перестановок, и я мог бы просто обрезать и удалить дубликаты, но тогда сложность заключается в следующем. слишком высокий (n!)

Я знаю, что проблема имеет хорошее решение, поскольку я видел, что это делается с помощью дополнительных модулей / библиотек в вопросах о перестановке строк

дополнительная информация: мне нужно только это для грубой силы неуравновешенной задачи присваивания, и венгерский алгоритм кажется слишком длинным, когда я вслух "решаю" проблему. Мой подход не приблизился к допустимому времени выполнения, потому что когда у меня есть массив, например, размером 8x3, моему алгоритму нужно 8! Сравнение, когда оно определенно может быть оптимизировано до гораздо меньшего числа.

Также это мой первый пост здесь после 3 лет CS, я разозлился на эту проблему, как миллион раз, поэтому я признал поражение и решил попросить вас переполнение стека Боги за помощь:>

Answer 1

Если вас не волнует вывод в лексикографическом порядке c, порядок здесь довольно простой:

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]);
    }

}

Тест ( OnlineGDB ):

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 

Answer 2

На практике у вас есть 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);
}

Answer 3

Я думаю, что вы можете сделать это в два этапа: сначала сгенерировать комбинацию из k элементов из набора n, а затем вывести перестановку каждой комбинации. Я проверил этот код и отлично работает:

#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

Answer 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}));
}