Generator for k-permutations without repetition

[bullockbefriending bard]

I was able to google a recipe for a k_permutations generator, such
that i can write:

x = range(1, 4) # (say)
[combi for combi in k_permutations(x, 3)] =>

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

but what i really want is the above without repetition, i.e.:

[combi for combi in k_permutations_without_repetitions(x, 3)] =>

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

For smallish lists, it's no problem to generate the list as follows:

no_reps_combis = [combi for combi in k_permutations(x, 3) if \

len(set(combi)) == 3]

but i'm sure there must be a way to do this as a pure generator, just
that i wouldn't have a clue how to go about it.

Help please, Python Gods!

Apologies in advance if I have got my terminology wrong and have been
googling the wrong stuff and therefore coming up blank.

 

[Gerard Flanagan]

I was able to google a recipe for a k_permutations generator, such
that i can write:

x = range(1, 4) # (say)
[combi for combi in k_permutations(x, 3)] =>

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

but what i really want is the above without repetition, i.e.:

[combi for combi in k_permutations_without_repetitions(x, 3)] =>

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

See `kslice` function here:

http://gflanagan.net/site/python/utils/sequtils/

Regards

Gerard

 

[=?ISO-8859-1?Q?Nis_J=F8rgensen?=]

bullockbefriending bard skrev:

I was able to google a recipe for a k_permutations generator, such
that i can write:

x = range(1, 4) # (say)
[combi for combi in k_permutations(x, 3)] =>

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

but what i really want is the above without repetition, i.e.:

[combi for combi in k_permutations_without_repetitions(x, 3)] =>

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

For smallish lists, it's no problem to generate the list as follows:

no_reps_combis = [combi for combi in k_permutations(x, 3) if \

len(set(combi)) == 3]

but i'm sure there must be a way to do this as a pure generator, just
that i wouldn't have a clue how to go about it.

Help please, Python Gods!

I was initially confused by your example, since the size of the
underlying set is the same as of the individual permutations. In this
case, you are just asking for all permutations of the set.

As far as I can tell from a quick googling, the relevant definition of
k-permutation is "an ordered list of k elements from the set". Thus your
first example does not really generate k_permutations.

A quick solution, not extensively tested

# base needs to be an of the python builtin set

def k_perm(base,k):
for e in base:
if k == 1:
yield [e]
else:
for perm in k_perm(base-set([e]),k-1):
yield [e] + perm

list(k_perm(set([1,2,3,4]),3))

[[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2,
1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3], [3, 1, 2],
[3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1,
3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]]


Much to my initial surprise, it "works" for k<1 as well:

list(k_perm(set([1,2,3,4]),-1))

[]

Hope this helps

Nis

 

[bullockbefriending bard]

bullockbefriending bard skrev:

I was able to google a recipe for a k_permutations generator, such
that i can write:

x = range(1, 4) # (say)
[combi for combi in k_permutations(x, 3)] =>

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

but what i really want is the above without repetition, i.e.:

[combi for combi in k_permutations_without_repetitions(x, 3)] =>

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

For smallish lists, it's no problem to generate the list as follows:

no_reps_combis = [combi for combi in k_permutations(x, 3) if \

len(set(combi)) == 3]

but i'm sure there must be a way to do this as a pure generator, just
that i wouldn't have a clue how to go about it.

Help please, Python Gods!

I was initially confused by your example, since the size of the
underlying set is the same as of the individual permutations. In this
case, you are just asking for all permutations of the set.

As far as I can tell from a quick googling, the relevant definition of
k-permutation is "an ordered list of k elements from the set". Thus your
first example does not really generate k_permutations.

A quick solution, not extensively tested

# base needs to be an of the python builtin set

def k_perm(base,k):
for e in base:
if k == 1:
yield [e]
else:
for perm in k_perm(base-set([e]),k-1):
yield [e] + perm

list(k_perm(set([1,2,3,4]),3))

[[1, 2, 3], [1, 2, 4], [1, 3, 2], [1, 3, 4], [1, 4, 2], [1, 4, 3], [2,
1, 3], [2, 1, 4], [2, 3, 1], [2, 3, 4], [2, 4, 1], [2, 4, 3], [3, 1, 2],
[3, 1, 4], [3, 2, 1], [3, 2, 4], [3, 4, 1], [3, 4, 2], [4, 1, 2], [4, 1,
3], [4, 2, 1], [4, 2, 3], [4, 3, 1], [4, 3, 2]]

Much to my initial surprise, it "works" for k<1 as well:

list(k_perm(set([1,2,3,4]),-1))

[]

Hope this helps

Nis

thank you!. i'll give this a try. seems to do exactly what i need.
sorry about the ambiguity in my example. i chose 3 from 3 merely to
keep the size of the example case small, without thinking enough about
how it might cause confusion.

 

[=?ISO-8859-1?Q?Nis_J=F8rgensen?=]

bullockbefriending bard skrev:

bullockbefriending bard skrev:
A quick solution, not extensively tested

# base needs to be an of the python builtin set

def k_perm(base,k):
for e in base:
if k == 1:
yield [e]
else:
for perm in k_perm(base-set([e]),k-1):
yield [e] + perm

thank you!. i'll give this a try. seems to do exactly what i need.
sorry about the ambiguity in my example. i chose 3 from 3 merely to
keep the size of the example case small, without thinking enough about
how it might cause confusion.

I managed to simplify it a little:

def k_perm(base,k):
if k == 0:
yield []
else:
for e in base:
for perm in k_perm(base-set([e]),k-1):
yield [e] + perm



Nis