数组元素的所有置换一次在C ++中占用一定数量的元素 [英] All Permutation of an array elements taken certain number of element at a time in C++

问题描述

我正在尝试一次获取一定数量元素的任何数组的所有置换集，例如，如果array = {1,2,3,4}和r=3，则可能的置换为24.这是我使用递归的实现，但这没有得到预期的结果.

I am trying to get all set of permutation of any array taken certain number of element at a time for example if array = {1,2,3,4} and r=3 then possible permutation will be 24. Here is my implementation using recursion but this is not giving expected result.

void permutationUtil(vector<int> arr, vector<int> data, int start, int end, int index, int r) {
    // Current permutation is ready to be printed, print it
     if (index == r){
    for (int j=0; j<r; j++)
        printf("%d ", data[j]);
    printf("\n");
    return;
}    
    // replace index with all possible elements. The condition
    // "end-i+1 >= r-index" makes sure that including one element
    // at index will make a permutation with remaining elements
    // at remaining positions  
    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        data[index] = arr[i];
        permutationUtil(arr, data, i + 1, end, index + 1, r);
    }
}

void printPermutation(vector<int> arr, int n, int r) {

    // A temporary array to store all permutation one by one
    vector<int> data(n);

    // Print all permutation using temprary array 'data[]'
    permutationUtil(arr, data, 0, n - 1, 0, r);
}

推荐答案

您可以使用std::next_permutation进行2次循环:

You may do it with 2 loop with std::next_permutation:

void permutationUtilInner(std::vector<int> v,
                          std::function<void (const std::vector<int>&)> f)
{
    do {
        f(v);
    } while (std::next_permutation(v.begin(), v.end()));
}

void permutationUtil(std::vector<int> v,
                     std::size_t r,
                     std::function<void (const std::vector<int>&)> f)
{
    // remainder: range should be sorted for std::next_permutation
    std::vector<bool> b(v.size() - r, false);
    b.resize(v.size(), true);

    std::sort(v.begin(), v.end());
    do {
        std::vector<int> sub;

        for (std::size_t i = 0; i != b.size(); ++i) {
            if (b[i]) {
                sub.push_back(v[i]);
            }
        }
        permutationUtilInner(sub, f);
    } while (std::next_permutation(b.begin(), b.end()));
}

演示

这篇关于数组元素的所有置换一次在C ++中占用一定数量的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！