CODEWITHSUNDEEP
algorithmiterationpermutation
I. Iudice
I. Iudice

Reputation: 55

Iterative algorithm for N choose K, without repetitions, order matters

I'm looking for an iterative algorithm to obtain all of the permutations of K elements extracted from a set of N elements, without repetitions (i.e., without substitutions), and for which order matters. I know the amount of permutations has to be N!/(N-K)!. Have you any ideas? Thank you.

Ivan

Upvotes: 1

Views: 907

Answers (1)

รยקคгรђשค
รยקคгรђשค

Reputation: 1979

Approach 1:

Simpler Idea:

Since the order matters, we will try to utilize next_permutation algorithm. The next_permutation function gives next lexicographically unique permutation.

Algorithm:

  1. Create a new array A of size equals to size of original array.
  2. Assign last k numbers 1,2,3,..k such that k ends last. Assign remaining numbers as 0.
  3. Now while iterating through permutations using next_permutation, select only indices in original array where value in A > 0, maintaning order.

Explanation for correctness:

Since in newly created array there are N numbers of which N-k are repeated, total unique permutations become N!/(N-k)! which gives us our desired outcome.

Example:

Input: X = [1,2,3], k=2

Now, we create A = [0,1,2].

All permutations:

[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0].

Choose only indices i of these permutations from original array where A[i] > 0, which will yield,

[2,3],
[3,2],
[1,3],
[1,2],
[3,1],
[2,1].

If you want above in sorted order, use negative numbers and initialize first k numbers with -k,-k-1,..-1 and remaining with 0 and apply the algorithm with slight modification, by selecting index i in original array, such that A[i] < 0 while maintaining order.

Sidenote: If order doesn't matter, initialize A with k -1s in the beginning and remaining 0 and use the iterative permutations algorithm which will generate unique possible k selections from N items.

Approach 2:(better than Approach 1)

Algorithm:

  1. Start by selecting first K numbers and populate in array A, it will store the index of chosen elements from original array. We mark it as the first selection.
  2. Now get all remaining permutations in lexicographical order.
  3. How to get next combination considering order? We will permute the selection if possible, otherwise return lexicographically greater selection.

Idea for getting next selection in lexicograhic order if permutations are exhausted:

We consider our current combination, and find the rightmost element that has not yet reached its highest possible value. Once finding this element, we increment it by 1, and assign the lowest valid value to all subsequent elements.

from: https://cp-algorithms.com/combinatorics/generating_combinations.html

Example:

Input: X = [1,2,3,4], k=3

Now, we create A = [0,1,2].

All permutations:

[0,1,2]    // initialization
[0,2,1]    // next permutation
...        // all permutations of [0,1,2]
...
[2,1,0]    // reached last permutation of current selection
[0,1,3]    // get next selection in lexicographic order as permutations are exhausted
...
[3,1,0]   // reached last permutation of current selection
[0,2,3]    // get next selection in lexicographic order as permutations are exhausted
...
[3,2,0]   // reached last permutation of current selection
[1,2,3]    // get next selection in lexicographic order as permutations are exhausted
...
[3,2,1]   // reached last permutation of current selection

Code (0-based indexing, so start with 0-k-1 initialization):

bool next_combination_with_order(vector<int>& a, int n, bool order_matters=true) {
    int k = (int)a.size();
    if(order_matters && std::next_permutation(a.begin(), a.end()))return True; // check if next permutation exists otherwise move forward and get next unique combination
    // if `a` was already in descending order, 
    // next_permutation returned false and changed the array to sorted order.
    // now find next combination if possible
    for (int i = k - 1; i >= 0; i--) {
        if (a[i] < n - k + i + 1) {
            a[i]++;
            for (int j = i + 1; j < k; j++)
                a[j] = a[j - 1] + 1;
            return true;
        }
    }
    return false;
}

References:

Next permutations:

https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

std::next_permutation Implementation Explanation

Next combination without order:

https://cp-algorithms.com/combinatorics/generating_combinations.html

Upvotes: 1

Related Questions