Generator for k-permutations without repetition

[Nis Jørgensen]

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