所有的數組元素的排列在C++中一次獲取了一定數量的元素

-1

我想要獲取任何數組的所有排列集合，例如如果array = {1,2,3,4}和r=3那麼可能的排列將是24。這是我使用遞歸的實現，但是這並沒有給出預期的結果。所有的數組元素的排列在C++中一次獲取了一定數量的元素

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

來源

2016-07-15 Ashutosh Pandey

你在尋找'std :: next_permutation'嗎？ – Arunmu

可能數組包含重複？ – Jarod42

@Arunmu std :: next_permuation在整個數組上執行排列，同時取得所有元素 –

您可以與2迴路用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())); 
}

Demo

來源

2016-07-15 08:17:03 Jarod42

謝謝..它完成了這項工作。 –

這是德爾福遞歸實現：

procedure Arrangement(var A: array of Integer; n, k: Integer; s: string); 
    var 
    i, t: Integer; 
    begin 
    if k = 0 then 
     Output(s) 
    else 
     for i := 0 to n - 1 do begin 
     t := A[i]; 
     A[i] := A[n - 1]; //store used item in the tail 
     Arrangement(A, n - 1, k - 1, s + IntToStr(t) + ' '); //recursion without tail 
     A[i] := t; //get it back 
     end; 
    end;

來源

2016-07-15 08:24:14 MBo

你的算法是不完整的。它一直在增加。不包括像2,1,3那樣需要不增加序列的情況。

在第二個for循環中，將int i=start更改爲int i=0以解決該問題。

來源

2016-07-15 08:50:21

所有的數組元素的排列在C++中一次獲取了一定數量的元素

回答

相關問題