On Jul 4, 7:09 pm, Nis Jørgensen <[EMAIL PROTECTED]> 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.
-- http://mail.python.org/mailman/listinfo/python-list
