Combinations of lists
88888 Dihedral
dihedral88888 at googlemail.com
Thu Oct 4 15:20:00 EDT 2012
On Thursday, October 4, 2012 11:12:41 PM UTC+8, Steen Lysgaard wrote:
> 2012/10/4 Joshua Landau <joshua.landau.ws at gmail.com>:
>
> > On 3 October 2012 21:15, Steen Lysgaard <boxeakasteen at gmail.com> wrote:
>
> >>
>
> >> Hi,
>
> >>
>
> >> thanks for your interest. Sorry for not being completely clear, yes
>
> >> the length of m will always be half of the length of h.
>
> >
>
> >
>
> > (Please don't top post)
>
> >
>
> > I have a solution to this, then.
>
> > It's not short or fast, but it's a lot faster than yours.
>
> >
>
> > But first let me explain the most obvious optimization to your version of
>
> > the code:
>
> >
>
> >> combs = set()
>
> >>
>
> >>
>
> >> for a in permutations(range(len(h)),len(h)):
>
> >> comb = []
>
> >> for i in range(len(h)):
>
> >> comb.append(c[i][a[i]])
>
> >> comb.sort()
>
> >>
>
> >> frzn = tuple(comb)
>
> >> if frzn not in combs:
>
> >> combs.add(frzn)
>
> >
>
> >
>
> > What I have done here is make your "combs" a set. This helps because you
>
> > are searching inside it and that is an O(N) operation... for lists.
>
> > A set can do the same in O(1). Simplez.
>
> >
>
> > first = list("AABBCCDDEE")
>
> > second = list("abcde")
>
> > import itertools
>
> > #
>
> > # Generator, so ignoring case convention
>
> > class force_unique_combinations:
>
> > def __init__(self, lst, n):
>
> > self.cache = set()
>
> > self.internal_iter = itertools.combinations(lst, n)
>
> > def __iter__(self):
>
> > return self
>
> > def __next__(self):
>
> > while True:
>
> > nxt = next(self.internal_iter)
>
> > if not nxt in self.cache:
>
> > self.cache.add(nxt)
>
> > return nxt
>
> > def combine(first, second):
>
> > sletter = second[0]
>
> > first_combinations = force_unique_combinations(first, 2)
>
> > if len(second) == 1:
>
> > for combination in first_combinations:
>
> > yield [sletter+combination[0], sletter+combination[1]]
>
> > else:
>
> > for combination in first_combinations:
>
> > first_ = first[:]
>
> > first_.remove(combination[0])
>
> > first_.remove(combination[1])
>
> > prefix = [sletter+combination[0], sletter+combination[1]]
>
> > for inner in combine(first_, second[1:]):
>
> > yield prefix + inner
>
> >
>
> >
>
> > This is quite naive, because I don't know how to properly implement
>
> > force_unique_combinations, but it runs. I hope this is right. If you need
>
> > significantly more speed your best chance is probably Cython or C, although
>
> > I don't doubt 10x more speed may well be possible from within Python.
>
> >
>
> >
>
> > Also, 88888 Dihedral is a bot, or at least pretending like crazy to be one.
>
>
>
> Great, I've now got a solution much faster than what I could come up with.
>
> Thanks to the both of you.
>
> And a good spot on 88... I could not for my life understand what he
>
> (it) had written.
>
>
>
> /Steen
If an unique order is defined, then it is trivial to solve this problem
without any recursions.
More information about the Python-list
mailing list