CODEWITHSUNDEEP
algorithmpermutationcombinatorics
zlon
zlon

Reputation: 834

Fast algorithm to generate all nonordered permutations of lenght K from N

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.

Upvotes: 0

Views: 260

Answers (2)

saga
saga

Reputation: 2113

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.

Upvotes: 1

Dan Getz
Dan Getz

Reputation: 18217

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]

Upvotes: 1

Related Questions