Generator for k-permutations without repetition

[bullockbefriending bard]

On Jul 4, 7:09 pm, Nis Jørgensen <n... at superlativ.dk> wrote:
> 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.