Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #60276 > unrolled thread

Re: Recursive generator for combinations of a multiset?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Recursive generator for combinations of a multiset? Dan Stromberg <drsalists@gmail.com> - 2013-11-22 22:33 -0800

#60276 — Re: Recursive generator for combinations of a multiset?

[Multipart message — attachments visible in raw view] — view raw

On Fri, Nov 22, 2013 at 4:58 PM, John O'Hagan <research@johnohagan.com>wrote:

> On Thu, 21 Nov 2013 12:59:26 -0800
> Dan Stromberg <drsalists@gmail.com> wrote:
>
> > On Wed, Nov 20, 2013 at 10:46 PM, John O'Hagan
> > <research@johnohagan.com>wrote:
> >
> > >
> > > Short story: the subject says it all, so if you have an answer
> > > already, fire away. Below is the long story of what I'm using it
> > > for, and why I think it needs to be recursive. It may even be of
> > > more general interest in terms of filtering the results of
> > > generators.
> > >
> >
> > I think you probably need permutations rather than combinations.
> >
> > Also, I think you'll need to form a word (partitioned off by spaces),
> > and then check it against a set containing /usr/share/dict/words
> > before recursing for the remainder of the sentence - this should
> > speed things up a LOT.
>
> Thanks for the reply. If I understand you correctly, you are suggesting
> permuting the input _characters_ to form words and then seeing if
> they exist, as opposed to my approach of combining known words and
> seeing if they are anagrams. (Permutations of words would not help find
> anagrams as they merely change the word order). Here is an attempt at
> that:


You've interpreted me correctly.

However, I was thinking about this in the back of my mind, and decided it
would probably be best to inhale /usr/share/dict/words (if on Linux), and
pull out words of the corrects lengths (as separated by the blanks) over
the correct (possible) alphabet, and permute Those, afterward checking if
they form good anagrams of the original sentence.  This would probably be
much faster, since English isn't that dense of a space.

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web