0

I have array of size N, I need to generate all permutations variants of size K from this array. Variants [1 2 3] and [3 1 2] are different. Standard solutions which I found were

1) Just permutations, where I obtain all reordering of the same size as array.

2) Just combinations, where I obtain all combinations of size K from array of size N, but for these algorithms [1 2 6] and [6 1 2] are the same, while I need them to be different.

Could You help me to find an effective solution?

I should implement it on Matlab, but I hope I will be able to translate Your solutions from other languages.

zlon
  • 812
  • 8
  • 24
  • Did you check the answers here ? https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n – mksteve Nov 27 '17 at 08:30

2 Answers2

1

Basically, in any language which can produce all unordered subsets of size K from 1:N, and which can produce all permutations of 1:K, getting all the ordered subsets is as simple as iterating over the subsets and permuting them using every K-permutation.

In Julia language:

using Combinatorics, Iterators, Base.Iterators

N = 4
K = 2

collect(flatten(permutations(subset) for subset in subsets(1:N,K)))

Gives:

12-element Array{Array{Int64,1},1}:
 [1, 2]
 [2, 1]
 [1, 3]
 [3, 1]
 [1, 4]
 [4, 1]
 [2, 3]
 [3, 2]
 [2, 4]
 [4, 2]
 [3, 4]
 [4, 3]
Dan Getz
  • 17,002
  • 2
  • 23
  • 41
1

Combine the two solutions you found. Here's the python code:

allPermutations = list()
combinations=getCombinations(arr, K)
for comb in combinations:
    allPermutations.extend(getPermutations(comb))

1.arr is the input array.

2.getCombinations is a function which returns a list of all the combinations in arr of size K.

3.getPermutations returns all permutations of the array given as input.

saga
  • 1,933
  • 2
  • 17
  • 44