Re: all possible combinations
Steven D'Aprano wrote: > On Thu, 28 Jul 2005 12:30:23 +0100, Steve Holden wrote: > > >>>This makes me wonder why we still don't have something like the unint >>>function above in the standard distribution. >>> >> >>Because it's not what you'd call (or, at least, it's not what I'd call) >>universally required. As you have shown it is relatively easy to hack >>something supp when it's needed, so since it isn't something that's >>required by the majority it hasn't been added to the library. > > > Have you looked at what's in the standard Python library? > > aifc.py => Stuff to parse AIFF-C and AIFF files. > imghdr.py => Recognize image file formats based on their first few bytes. > gopher.py => Gopher protocol client interface. > token.py => Token constants (from "token.h"). > > I'm sure they are useful to somebody, but do you really think that the > majority of Python users need to parse AIFF files? > > Converting base-19 strings into integers is a rather niche need, but if > somebody bothered to write, document and provide unittests for such a > module, I'm sure it could be added to the standard library. It isn't as if > there is any policy of prohibiting specialist modules just because they > don't have universal need. > > And no, I'm not volunteering. I may, if I get an itch, but at this moment > in my life I'm not that fussed one way or another. > > > Well, here I have to fall back on history. I only started using Python in the mid-to-late 1990's. In those days modules were added to the language because they existed, and it was an easy way to distribute them. Now Python has a significant user base the development of the language, and the structure of the libraries, comes under more scrutiny, and there is a general feeling that parsimony is to be preferred to bloat. I can hardly disagree with you that aifc.py represents bloat by today's standards, and I don't think I could name a single gopher user (though that was certainly NOT the case in the mid-1990s). and-i-still-can't-find-an-email-tool-with-dwim-ly y'rs - steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC http://www.holdenweb.com/ -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Steven D'Aprano wrote: > Have you looked at what's in the standard Python library? > > aifc.py => Stuff to parse AIFF-C and AIFF files. > imghdr.py => Recognize image file formats based on their first few bytes. > gopher.py => Gopher protocol client interface. > token.py => Token constants (from "token.h"). > > I'm sure they are useful to somebody, but do you really think that the > majority of Python users need to parse AIFF files? There's a *huge* difference between, "Should we add such-and-such module?" and "Should we keep such-and-such module?" The burden for the latter is much, much lower. Some of those modules are there because Python itself needs them (token.py). Some are there because way back in the day before python-dev got disciplined (or, for that matter, existed), a sufficient criterion for inclusion into the standard library was, "Guido uses it." He needed to parse AIFF files and various arcane image formats and do graphics using the old SGI GL (the precursor to OpenGL). That's why some of that stuff is there. That said, I really would like a nice standard way to get the base-n representations of numbers for at least 2 <= n <= 36. -- Robert Kern [EMAIL PROTECTED] "In the fields of hell where the grass grows high Are the graves of dreams allowed to die." -- Richard Harter -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Thu, 28 Jul 2005 12:30:23 +0100, Steve Holden wrote: >> This makes me wonder why we still don't have something like the unint >> function above in the standard distribution. >> > Because it's not what you'd call (or, at least, it's not what I'd call) > universally required. As you have shown it is relatively easy to hack > something supp when it's needed, so since it isn't something that's > required by the majority it hasn't been added to the library. Have you looked at what's in the standard Python library? aifc.py => Stuff to parse AIFF-C and AIFF files. imghdr.py => Recognize image file formats based on their first few bytes. gopher.py => Gopher protocol client interface. token.py => Token constants (from "token.h"). I'm sure they are useful to somebody, but do you really think that the majority of Python users need to parse AIFF files? Converting base-19 strings into integers is a rather niche need, but if somebody bothered to write, document and provide unittests for such a module, I'm sure it could be added to the standard library. It isn't as if there is any policy of prohibiting specialist modules just because they don't have universal need. And no, I'm not volunteering. I may, if I get an itch, but at this moment in my life I'm not that fussed one way or another. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Steve Holden wrote: > > This makes me wonder why we still don't have something like the unint > > function above in the standard distribution. > > > Because it's not what you'd call (or, at least, it's not what I'd call) > universally required. As you have shown it is relatively easy to hack > something supp when it's needed, so since it isn't something that's > required by the majority it hasn't been added to the library. How about the symmetry argument? One can use int for radix 1 to 32 (I think) but for the reverse problem we only have hex or oct (and cannot choose symbol lists but that's not so very important, if the whole matter has any significance of course :-). Hey, unint might even win the "more general" approval! Anton "or maybe it's just because it's difficult to find a good name for it" -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Anton Vredegoor wrote:
> John Machin wrote:
>
>
>>You don't need to use random sampling. Paul Rubin has shown how it can
>>be done deterministically. The following is a generalisation of his
>>code; it generates all possible assemblies of size n from a list of
>>parts. Is this helpful?
>>
>>def all_size_n_knickers(rqd_size, pieces):
>> npieces = len(pieces)
>> knicker_count = npieces ** rqd_size
>> austen = [npieces ** (rqd_size-k-1) for k in xrange(rqd_size)]
>> for i in xrange(knicker_count):
>> knicker = [pieces[j] for j in [(i // d) % npieces for d in austen]]
>> yield knicker
>>
>>for alist in all_size_n_knickers(4, 'abc'):
>> print ''.join(alist)
>>
>>print
>>print list(all_size_n_knickers(2, [1, 42, 666]))
>
>
> Just testing out my ELCH JythonConsole :-)
>
> def unint(i,symbols):
> res = []
> radix = len(symbols)
> while i:
> i,r = divmod(i,radix)
> res.append(symbols[r])
> return res[::-1]
>
> start = int('1',3)
> finish = int('2',3)
> for i in range(start,finish):
> print ''.join(unint(i,'abc')[1:])
>
> This makes me wonder why we still don't have something like the unint
> function above in the standard distribution.
>
Because it's not what you'd call (or, at least, it's not what I'd call)
universally required. As you have shown it is relatively easy to hack
something supp when it's needed, so since it isn't something that's
required by the majority it hasn't been added to the library.
regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC http://www.holdenweb.com/
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
John Machin wrote:
> You don't need to use random sampling. Paul Rubin has shown how it can
> be done deterministically. The following is a generalisation of his
> code; it generates all possible assemblies of size n from a list of
> parts. Is this helpful?
>
> def all_size_n_knickers(rqd_size, pieces):
> npieces = len(pieces)
> knicker_count = npieces ** rqd_size
> austen = [npieces ** (rqd_size-k-1) for k in xrange(rqd_size)]
> for i in xrange(knicker_count):
> knicker = [pieces[j] for j in [(i // d) % npieces for d in austen]]
> yield knicker
>
> for alist in all_size_n_knickers(4, 'abc'):
> print ''.join(alist)
>
> print
> print list(all_size_n_knickers(2, [1, 42, 666]))
Just testing out my ELCH JythonConsole :-)
def unint(i,symbols):
res = []
radix = len(symbols)
while i:
i,r = divmod(i,radix)
res.append(symbols[r])
return res[::-1]
start = int('1',3)
finish = int('2',3)
for i in range(start,finish):
print ''.join(unint(i,'abc')[1:])
This makes me wonder why we still don't have something like the unint
function above in the standard distribution.
Anton
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Wow. That's neat. I'm going to use it. Thanks!
On Thu, 2005-07-14 at 19:52 -0400, Peter Hansen wrote:
> Bengt Richter wrote:
> > On Thu, 14 Jul 2005 17:10:37 -0400, William Park <[EMAIL PROTECTED]> wrote:
> > It's a one liner in Python too ;-)
> >
> > >>> print ' '.join([x+y+z+q for s in ['abc'] for x in s for y in s for z
> > in s for q in s])
>
> Or for the cost of an import and a lambda, you can keep it looking real
> obscure and generalize it to any size of sequence ('abcdef' or whatever)
> and a result length of up to 52 elements:
>
> >>> from string import letters as L
> >>> cartesian = lambda seq, num: eval("list(%s for __ in [seq]
> %s)" % ('+'.join(L[:num]), 'for %s in __ ' * num % tuple(L[:num])))
> # (there are spaces at any line breaks above)
>
> >>> cartesian('abcde', 6)
> ['aa', 'ab', 'ac', 'ad', 'ae', 'ba',
> ...
> 'ec', 'ed', 'ee']
> >>> len(_)
> 15625
>
>
>
> -Peter
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Bengt Richter wrote:
> On Thu, 14 Jul 2005 17:10:37 -0400, William Park <[EMAIL PROTECTED]> wrote:
> It's a one liner in Python too ;-)
>
> >>> print ' '.join([x+y+z+q for s in ['abc'] for x in s for y in s for z in
> s for q in s])
Or for the cost of an import and a lambda, you can keep it looking real
obscure and generalize it to any size of sequence ('abcdef' or whatever)
and a result length of up to 52 elements:
>>> from string import letters as L
>>> cartesian = lambda seq, num: eval("list(%s for __ in [seq]
%s)" % ('+'.join(L[:num]), 'for %s in __ ' * num % tuple(L[:num])))
# (there are spaces at any line breaks above)
>>> cartesian('abcde', 6)
['aa', 'ab', 'ac', 'ad', 'ae', 'ba',
...
'ec', 'ed', 'ee']
>>> len(_)
15625
-Peter
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Thu, 14 Jul 2005 17:10:37 -0400, William Park <[EMAIL PROTECTED]> wrote:
>rbt <[EMAIL PROTECTED]> wrote:
>> Say I have a list that has 3 letters in it:
>>
>> ['a', 'b', 'c']
>>
>> I want to print all the possible 4 digit combinations of those 3
>> letters:
>>
>> 4^3 = 64
>>
>>
>> abaa
>> aaba
>> aaab
>> acaa
>> aaca
>> aaac
>> ...
>>
>> What is the most efficient way to do this?
>
>Since you're doing cross product (ie. 3*3*3*3), manual loop of 4 level
>deep would be the fastest in terms of algorithm. C vs. Python is
>implementation detail.
>
>In Bash shell, this is one-liner,
>echo {a,b,c}{a,b,c}{a,b,c}{a,b,c}
>or maybe two,
>abc=(a b c)
>echo {^abc}{^abc}{^abc}{^abc}
>
It's a one liner in Python too ;-)
>>> print ' '.join([x+y+z+q for s in ['abc'] for x in s for y in s for z in s
>>> for q in s])
aaab aaac aaba aabb aabc aaca aacb aacc abaa abab abac abba abbb abbc
abca abcb abcc acaa a
cab acac acba acbb acbc acca accb accc baaa baab baac baba babb babc baca bacb
bacc bbaa bbab bb
ac bbba bbbc bbca bbcb bbcc bcaa bcab bcac bcba bcbb bcbc bcca bccb bccc
caaa caab caac cab
a cabb cabc caca cacb cacc cbaa cbab cbac cbba cbbb cbbc cbca cbcb cbcc ccaa
ccab ccac ccba ccbb
ccbc ccca cccb
Regards,
Bengt Richter
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt wrote:
> Thanks to all who were helpful... some of you guys are too harsh and
> cynical.
Reality check: wander down to your nearest military establishment, ask a
drill sergeant to demonstrate "harsh and cynical".
> Here's what I came up with. I believe it's a proper
> combination, but I'm sure someone will point out that I'm wrong ;)
>
> groups = [list('abc'),list('abc'),list('abc'),list('abc')]
>
> already = []
In general, a set would be better than a list (1) conceptually (2) when
the number of elements is large.
>
> while 1:
>
> LIST = []
Read the style guide -- http://www.python.org/peps/pep-0008.html
>
> for g in groups:
> sample = random.sample(g, 1)
> LIST.append(sample[0])
>
> STRING = ''.join(LIST)
> if STRING not in already:
> print STRING
> already.append(STRING)
> if len(already) == 81:
> break
>
You don't need to use random sampling. Paul Rubin has shown how it can
be done deterministically. The following is a generalisation of his
code; it generates all possible assemblies of size n from a list of
parts. Is this helpful?
def all_size_n_knickers(rqd_size, pieces):
npieces = len(pieces)
knicker_count = npieces ** rqd_size
austen = [npieces ** (rqd_size-k-1) for k in xrange(rqd_size)]
for i in xrange(knicker_count):
knicker = [pieces[j] for j in [(i // d) % npieces for d in austen]]
yield knicker
for alist in all_size_n_knickers(4, 'abc'):
print ''.join(alist)
print
print list(all_size_n_knickers(2, [1, 42, 666]))
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
"rbt" <[EMAIL PROTECTED]> wrote:
> Thanks to all who were helpful... some of you guys are too harsh and
> cynical. Here's what I came up with. I believe it's a proper
> combination, but I'm sure someone will point out that I'm wrong ;)
>
> groups = [list('abc'),list('abc'),list('abc'),list('abc')]
>
> already = []
>
> while 1:
>
> LIST = []
>
> for g in groups:
> sample = random.sample(g, 1)
> LIST.append(sample[0])
>
> STRING = ''.join(LIST)
> if STRING not in already:
> print STRING
> already.append(STRING)
> if len(already) == 81:
> break
UGH! I guess you're right, it's theoretically correct in the limit;
however IIRC, in your original post you were asking about the most
efficient way, not the least efficient, most obscure and inextensible
solution one could come up with. You're hoping to generate all
combinations AT RANDOM and you're wondering why some of us come out
"too harsh and cynical" ?! Try this with all letters instead of 'abc'
and when it ends get back to us, or rather our grand-grandchildren. In
the meantime, learn about recursion, generators and accumulating loops
and try to understand the right, efficient solutions already posted.
Cynically yrs,
George
PS: Btw, using ALL_CAPITALS (at least for local variables) is BAD
STYLE; the same holds for variables named 'list' and 'string',
independent of case.
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
William Park wrote: > Since you're doing cross product (ie. 3*3*3*3), manual loop of 4 level > deep would be the fastest in terms of algorithm. That's a Cartesian product, actually :-). -- Erik Max Francis && [EMAIL PROTECTED] && http://www.alcyone.com/max/ San Jose, CA, USA && 37 20 N 121 53 W && AIM erikmaxfrancis All generalizations are dangerous, even this one. -- Dumas Fils -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt <[EMAIL PROTECTED]> wrote:
> Say I have a list that has 3 letters in it:
>
> ['a', 'b', 'c']
>
> I want to print all the possible 4 digit combinations of those 3
> letters:
>
> 4^3 = 64
>
>
> abaa
> aaba
> aaab
> acaa
> aaca
> aaac
> ...
>
> What is the most efficient way to do this?
Since you're doing cross product (ie. 3*3*3*3), manual loop of 4 level
deep would be the fastest in terms of algorithm. C vs. Python is
implementation detail.
In Bash shell, this is one-liner,
echo {a,b,c}{a,b,c}{a,b,c}{a,b,c}
or maybe two,
abc=(a b c)
echo {^abc}{^abc}{^abc}{^abc}
--
William Park <[EMAIL PROTECTED]>, Toronto, Canada
ThinFlash: Linux thin-client on USB key (flash) drive
http://home.eol.ca/~parkw/thinflash.html
BashDiff: Super Bash shell
http://freshmeat.net/projects/bashdiff/
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt wrote: > Say I have a list that has 3 letters in it: > > ['a', 'b', 'c'] > > I want to print all the possible 4 digit combinations of those 3 > letters: When I have occasion to do an iteration of iterations, I either use recursion (already posted) or use an accumulator type loop: items = ['a','b','c'] accume = [[],] for pos in range(4): old_accume, accume = accume, [] for comb in old_accume: for item in items: accume.append(comb + [item]) accume = [''.join(x) for x in accume] print accume ['', 'aaab', 'aaac', 'aaba', 'aabb', 'aabc', 'aaca', 'aacb', 'aacc', 'abaa', 'abab', 'abac', 'abba', 'abbb', 'abbc', 'abca', 'abcb', 'abcc', 'acaa', 'acab', 'acac', 'acba', 'acbb', 'acbc', 'acca', 'accb', 'accc', 'baaa', 'baab', 'baac', 'baba', 'babb', 'babc', 'baca', 'bacb', 'bacc', 'bbaa', 'bbab', 'bbac', 'bbba', '', 'bbbc', 'bbca', 'bbcb', 'bbcc', 'bcaa', 'bcab', 'bcac', 'bcba', 'bcbb', 'bcbc', 'bcca', 'bccb', 'bccc', 'caaa', 'caab', 'caac', 'caba', 'cabb', 'cabc', 'caca', 'cacb', 'cacc', 'cbaa', 'cbab', 'cbac', 'cbba', 'cbbb', 'cbbc', 'cbca', 'cbcb', 'cbcc', 'ccaa', 'ccab', 'ccac', 'ccba', 'ccbb', 'ccbc', 'ccca', 'cccb', ''] Optimize as you see fit. -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt <[EMAIL PROTECTED]> writes: > Say I have a list that has 3 letters in it: > > ['a', 'b', 'c'] > > I want to print all the possible 4 digit combinations of those 3 > letters: for i in xrange(81): print ''.join(['abcd'[j] for j in [(i//d)%3 for d in (27,9,3,1)]]) -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Thanks to all who were helpful... some of you guys are too harsh and
cynical. Here's what I came up with. I believe it's a proper
combination, but I'm sure someone will point out that I'm wrong ;)
groups = [list('abc'),list('abc'),list('abc'),list('abc')]
already = []
while 1:
LIST = []
for g in groups:
sample = random.sample(g, 1)
LIST.append(sample[0])
STRING = ''.join(LIST)
if STRING not in already:
print STRING
already.append(STRING)
if len(already) == 81:
break
On Thu, 2005-07-14 at 23:18 +1000, John Machin wrote:
> Steven D'Aprano wrote:
> > On Thu, 14 Jul 2005 08:49:05 +1000, John Machin wrote:
> >
> >
> >>"You keep using that word. I do not think it means what you think it means."
> >>
> >>Both of you please google("define: combination")
> >
> >
> > Combination: "a coordinated sequence of chess moves".
> >
> > "An option position that is effected by either a purchase of two long
> > positions or two short positions. The investor purchases a call and a put
> > (or sells a call and a put) with different expiration dates and/or
> > different strike prices."
> >
> > Or perhaps "in Scheme, a function call, consisting of a function name and
> > arguments written within parentheses."
> >
> > Yes, mathematically the definition of combination includes that order does
> > not matter. But that certainly isn't the case in common English. Now,
> > John, given the tone of the posts you are complaining about,
>
> Wrong -- no complaint. Another quote: "It's a joke, Joyce!"
>
> > do you think
> > I was using combination in the precise mathematical sense, or the common
> > English sense?
>
> As in "Please don't get your combinations in a twist?"?
>
> >
> > (Hint: the very first definition Google finds is "a collection of things
> > that have been combined; an assemblage of separate parts or qualities ".
> > Not a word there about order mattering or not.)
>
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Steven D'Aprano wrote:
> On Thu, 14 Jul 2005 08:49:05 +1000, John Machin wrote:
>
>
>>"You keep using that word. I do not think it means what you think it means."
>>
>>Both of you please google("define: combination")
>
>
> Combination: "a coordinated sequence of chess moves".
>
> "An option position that is effected by either a purchase of two long
> positions or two short positions. The investor purchases a call and a put
> (or sells a call and a put) with different expiration dates and/or
> different strike prices."
>
> Or perhaps "in Scheme, a function call, consisting of a function name and
> arguments written within parentheses."
>
> Yes, mathematically the definition of combination includes that order does
> not matter. But that certainly isn't the case in common English. Now,
> John, given the tone of the posts you are complaining about,
Wrong -- no complaint. Another quote: "It's a joke, Joyce!"
> do you think
> I was using combination in the precise mathematical sense, or the common
> English sense?
As in "Please don't get your combinations in a twist?"?
>
> (Hint: the very first definition Google finds is "a collection of things
> that have been combined; an assemblage of separate parts or qualities ".
> Not a word there about order mattering or not.)
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Thu, 14 Jul 2005 08:49:05 +1000, John Machin wrote:
> "You keep using that word. I do not think it means what you think it means."
>
> Both of you please google("define: combination")
Combination: "a coordinated sequence of chess moves".
"An option position that is effected by either a purchase of two long
positions or two short positions. The investor purchases a call and a put
(or sells a call and a put) with different expiration dates and/or
different strike prices."
Or perhaps "in Scheme, a function call, consisting of a function name and
arguments written within parentheses."
Yes, mathematically the definition of combination includes that order does
not matter. But that certainly isn't the case in common English. Now,
John, given the tone of the posts you are complaining about, do you think
I was using combination in the precise mathematical sense, or the common
English sense?
(Hint: the very first definition Google finds is "a collection of things
that have been combined; an assemblage of separate parts or qualities ".
Not a word there about order mattering or not.)
--
Steven.
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
* Thomas Bartkus (2005-07-13 20:20 +0100) > "George Sakkis" <[EMAIL PROTECTED]> wrote in message > news:[EMAIL PROTECTED] >> "rbt" <[EMAIL PROTECTED]> wrote: >> >>> Say I have a list that has 3 letters in it: >>> >>> ['a', 'b', 'c'] >>> >>> I want to print all the possible 4 digit combinations of those 3 >>> letters: >>> >>> 4^3 = 64 >> >> >> It's actually 3^4 = 81 (3 candidates/choice ** 4 choices) > > Yes. You get a cigar! > > Someone else (Jack Diederich) also mentioned "This is called a cartesian > product, ..." > Right again. In set theory it's called "cartesian product" while in combinatorics it's called "variation with repetition". There is some "die-hard" terminology confusion about permutations, combinations and variations (see [1] for example). (luckily at least most of the Python "officials" (GvR and Frederik Lundh) seem to agree about this terminology) Thorsten [1] http://groups-beta.google.com/group/comp.lang.python/msg/dea80dec0192eda6?hl=en&; -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
John Machin <[EMAIL PROTECTED]> writes: >>>My list is not arbitrary. I'm looking for all 'combinations' as I >>>originally posted. Order does not matter to me... just all possibilities. >> That's good, since you only need combinations of "a", "b" and "c" the > "You keep using that word. I do not think it means what you think it means." Inconceivable! -- # Edvard Majakari Software Engineer # PGP PUBLIC KEY available Soli Deo Gloria! "Debugging is twice as hard as writing the code in the firstplace. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." -- Brian W. Kernighan -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt wrote:
> On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
>
>>Say I have a list that has 3 letters in it:
>>
>>['a', 'b', 'c']
>>
>>I want to print all the possible 4 digit combinations of those 3
>>letters:
>>
>>4^3 = 64
>>
>>
>>abaa
>>aaba
>>aaab
>>acaa
>>aaca
>>aaac
>>...
>>
>>What is the most efficient way to do this?
>
>
> Expanding this to 4^4 (256) to test the random.sample function produces
> interesting results. It never finds more than 24 combinations out of the
Uh-oh -- there's that word again! What you mean to say is that it never
finds more than 24 *PERMUTATIONS*.
1. google("define: permutation")
2. Consider that 24 == 4 * 3 * 2 * 1
3. RTFM("random.sample"), paying particular attention to the word "unique"
> possible 256. This leads to the question... how 'random' is sample ;)
>
> Try it for yourselves:
>
> test = list('1234')
>
> combinations = []
> while 1:
> combo = random.sample(test, 4)
> possibility = ''.join(combo)
> if possibility not in combinations:
> print possibility
> combinations.append(possibility)
> continue
> else:
> continue
>
Instead of the utterly pointless continue/else/continue, shouldn't you
have some method (other than keyboard interrupt) of jumping off the
merry-go-round?
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Steven D'Aprano wrote:
> On Wed, 13 Jul 2005 10:39:41 -0400, rbt wrote:
[snip]
> Ah, then that's easy. Sit down with pencil and paper, write out all 64
> combinations yourself, and then type them into a Python list. Then you can
> access any one of those combinations with a single call.
[snip]
>>My list is not arbitrary. I'm looking for all 'combinations' as I
>>originally posted. Order does not matter to me... just all possibilities.
>
>
> That's good, since you only need combinations of "a", "b" and "c" the
"You keep using that word. I do not think it means what you think it means."
Both of you please google("define: combination")
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt wrote: > Say I have a list that has 3 letters in it: > > ['a', 'b', 'c'] > > I want to print all the possible 4 digit combinations of those 3 > letters: > > 4^3 = 64 Should be 3**4 = 81. > > > abaa > aaba > aaab > acaa > aaca > aaac > ... > > What is the most efficient way to do this? Table t [c] a b c Query q SELECT t_3.c AS c1, t_2.c AS c2, t_1.c AS c3, t.c AS c4 FROM t, t AS t_1, t AS t_2, t AS t_3; output [c1][c2][c3][c4] a a a a a a a b a a a c a a b a a a b b a a b c a a c a a a c b a a c c a b a a a b a b a b a c a b b a a b b b a b b c a b c a a b c b a b c c a c a a a c a b a c a c a c b a a c b b a c b c a c c a a c c b a c c c b a a a b a a b b a a c b a b a b a b b b a b c b a c a b a c b b a c c b b a a b b a b b b a c b b b a b b b b b b b c b b c a b b c b b b c c b c a a b c a b b c a c b c b a b c b b b c b c b c c a b c c b b c c c c a a a c a a b c a a c c a b a c a b b c a b c c a c a c a c b c a c c c b a a c b a b c b a c c b b a c b b b c b b c c b c a c b c b c b c c c c a a c c a b c c a c c c b a c c b b c c b c c c c a c c c b c c c c Record 81 of 81 -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
"George Sakkis" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > "rbt" <[EMAIL PROTECTED]> wrote: > > > Say I have a list that has 3 letters in it: > > > > ['a', 'b', 'c'] > > > > I want to print all the possible 4 digit combinations of those 3 > > letters: > > > > 4^3 = 64 > > > It's actually 3^4 = 81 (3 candidates/choice ** 4 choices) Yes. You get a cigar! Someone else (Jack Diederich) also mentioned "This is called a cartesian product, ..." Right again. Now I can't help injecting that SQL is custom made for returning a cartesian product. Given a table called [Letters] containing a field [Letter] with (3) records Letter = 'a', 'b', 'c' SELECT CONCAT(t1.Letter, t2.Letter, t3.Letter, t4.Letter) FROM Letters As t1, Letters As t2, Letters As t3, Letters As t4 Will return those 81 combinations in an eyblink. In order to stay on topic, you are required to call your favorite SQL engine from Python :-) Thomas Bartkus -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
"rbt" <[EMAIL PROTECTED]> wrote:
> Say I have a list that has 3 letters in it:
>
> ['a', 'b', 'c']
>
> I want to print all the possible 4 digit combinations of those 3
> letters:
>
> 4^3 = 64
It's actually 3^4 = 81 (3 candidates/choice ** 4 choices)
>
> abaa
> aaba
> aaab
> acaa
> aaca
> aaac
> ...
>
> What is the most efficient way to do this?
I don't know if it's *the most* efficient -- and I don't think it really
matters -- but it's fast,
short and sweet:
def iterPermutations(num, seq):
if num:
for rest in iterPermutations(num-1, seq):
for item in seq:
yield rest + [item]
else:
yield []
for comb in iterPermutations(4, list("abc")):
print ''.join(comb)
George
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
Jack Diederich wrote:
> On Wed, Jul 13, 2005 at 05:07:33PM +0100, Duncan Smith wrote:
>
>>rbt wrote:
>>
>>>On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:
>>>
>>>
On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
>Say I have a list that has 3 letters in it:
>
>['a', 'b', 'c']
>
>I want to print all the possible 4 digit combinations of those 3
>letters:
>
>4^3 = 64
>
>
>abaa
>aaba
>aaab
>acaa
>aaca
>aaac
>...
>
>What is the most efficient way to do this?
Expanding this to 4^4 (256) to test the random.sample function produces
interesting results. It never finds more than 24 combinations out of the
possible 256. This leads to the question... how 'random' is sample ;)
Try it for yourselves:
test = list('1234')
combinations = []
while 1:
combo = random.sample(test, 4)
possibility = ''.join(combo)
if possibility not in combinations:
print possibility
combinations.append(possibility)
continue
else:
continue
>>>
>>>
>>>Someone pointed out off-list that this is doing permutation, not
>>>combination. Is there a way to make random.sample to do combinations?
>>>
>>
>>Probably not in any sensible way. But what you list in your original
>>post are not distinct combinations. e.g. abaa and aaba are both 3 a's
>>and 1 b. Maybe you mean that order does matter (and you're actually
>>looking for all distinct permutations of all combinations)?
>>
>
> This is called a cartesian product, and the easiest way is to do
>
> import probstat # probstat.sourceforge.net
> letters = list('abcd')
> for (guys) in probstat.Cartesian([letters] * 4):
> print ''.join(guys)
>
> It's a C module I wrote to do this stuff a few years ago, still compiles
> and runs just fine (at least on linux).
>
> -jackdied
Yep. probstat also ran on Windows the last time I used it :-).
Duncan
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Wed, Jul 13, 2005 at 05:07:33PM +0100, Duncan Smith wrote:
> rbt wrote:
> > On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:
> >
> >>On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
> >>
> >>>Say I have a list that has 3 letters in it:
> >>>
> >>>['a', 'b', 'c']
> >>>
> >>>I want to print all the possible 4 digit combinations of those 3
> >>>letters:
> >>>
> >>>4^3 = 64
> >>>
> >>>
> >>>abaa
> >>>aaba
> >>>aaab
> >>>acaa
> >>>aaca
> >>>aaac
> >>>...
> >>>
> >>>What is the most efficient way to do this?
> >>
> >>Expanding this to 4^4 (256) to test the random.sample function produces
> >>interesting results. It never finds more than 24 combinations out of the
> >>possible 256. This leads to the question... how 'random' is sample ;)
> >>
> >>Try it for yourselves:
> >>
> >>test = list('1234')
> >>
> >>combinations = []
> >>while 1:
> >>combo = random.sample(test, 4)
> >>possibility = ''.join(combo)
> >>if possibility not in combinations:
> >>print possibility
> >>combinations.append(possibility)
> >>continue
> >>else:
> >>continue
> >>
> >
> >
> > Someone pointed out off-list that this is doing permutation, not
> > combination. Is there a way to make random.sample to do combinations?
> >
> Probably not in any sensible way. But what you list in your original
> post are not distinct combinations. e.g. abaa and aaba are both 3 a's
> and 1 b. Maybe you mean that order does matter (and you're actually
> looking for all distinct permutations of all combinations)?
>
This is called a cartesian product, and the easiest way is to do
import probstat # probstat.sourceforge.net
letters = list('abcd')
for (guys) in probstat.Cartesian([letters] * 4):
print ''.join(guys)
It's a C module I wrote to do this stuff a few years ago, still compiles
and runs just fine (at least on linux).
-jackdied
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt wrote: > Expanding this to 4^4 (256) to test the random.sample function produces > interesting results. It never finds more than 24 combinations out of the > possible 256. This leads to the question... how 'random' is sample ;) sample(population,k): Return a k length list of unique elements chosen from the population sequence. Used for random sampling without replacement. New in version 2.3. Working as designed, I'd say. 4! = 24. -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt wrote:
> On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:
>
>>On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
>>
>>>Say I have a list that has 3 letters in it:
>>>
>>>['a', 'b', 'c']
>>>
>>>I want to print all the possible 4 digit combinations of those 3
>>>letters:
>>>
>>>4^3 = 64
>>>
>>>
>>>abaa
>>>aaba
>>>aaab
>>>acaa
>>>aaca
>>>aaac
>>>...
>>>
>>>What is the most efficient way to do this?
>>
>>Expanding this to 4^4 (256) to test the random.sample function produces
>>interesting results. It never finds more than 24 combinations out of the
>>possible 256. This leads to the question... how 'random' is sample ;)
>>
>>Try it for yourselves:
>>
>>test = list('1234')
>>
>>combinations = []
>>while 1:
>>combo = random.sample(test, 4)
>>possibility = ''.join(combo)
>>if possibility not in combinations:
>>print possibility
>>combinations.append(possibility)
>>continue
>>else:
>>continue
>>
>
>
> Someone pointed out off-list that this is doing permutation, not
> combination. Is there a way to make random.sample to do combinations?
>
Probably not in any sensible way. But what you list in your original
post are not distinct combinations. e.g. abaa and aaba are both 3 a's
and 1 b. Maybe you mean that order does matter (and you're actually
looking for all distinct permutations of all combinations)?
Duncan
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
rbt wrote:
> On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
>
>>Say I have a list that has 3 letters in it:
>>
>>['a', 'b', 'c']
>>
>>I want to print all the possible 4 digit combinations of those 3
>>letters:
>>
>>4^3 = 64
>>
>>
>>abaa
>>aaba
>>aaab
>>acaa
>>aaca
>>aaac
>>...
>>
>>What is the most efficient way to do this?
>
>
> Expanding this to 4^4 (256) to test the random.sample function produces
> interesting results. It never finds more than 24 combinations out of the
> possible 256. This leads to the question... how 'random' is sample ;)
>
> Try it for yourselves:
>
> test = list('1234')
>
> combinations = []
> while 1:
> combo = random.sample(test, 4)
> possibility = ''.join(combo)
> if possibility not in combinations:
> print possibility
> combinations.append(possibility)
> continue
> else:
> continue
>
There are only 24 possible lists that random.sample(test, 4) can return,
corresponding to the 24 possible orderings of 4 items. i.e.
random.sample() samples without replacement. You need to sample with
replacement.
Duncan
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Wed, 13 Jul 2005 11:09:25 -0400, rbt wrote:
> On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
>> Say I have a list that has 3 letters in it:
>>
>> ['a', 'b', 'c']
>>
>> I want to print all the possible 4 digit combinations of those 3
>> letters:
[snip]
> Expanding this to 4^4 (256) to test the random.sample function produces
> interesting results. It never finds more than 24 combinations out of the
> possible 256. This leads to the question... how 'random' is sample ;)
See below.
> Try it for yourselves:
>
> test = list('1234')
>
> combinations = []
> while 1:
> combo = random.sample(test, 4)
> possibility = ''.join(combo)
> if possibility not in combinations:
> print possibility
> combinations.append(possibility)
> continue
> else:
> continue
That's not very efficient code. Why not just write it like this?
combinations = []
while 1:
combo = random.sample(test, 4)
possibility = ''.join(combo)
if possibility not in combinations:
print possibility
combinations.append(possibility)
You don't need either of the two continue statements.
But in fact, random.sample is correct.
You have four items to choose from: "1", "2", "3", "4".
If you choose them with replacement, then there are 4*4*4*4 = 256
possibilities, but that includes duplicates:
[4, 4, 4, 4] is one such possibility.
As the documentation for random.sample clearly says:
"sample(self, population, k) method of random.Random instance
Chooses k unique random elements from a population sequence."
Notice the UNIQUE part? You should have realised that just by looking at
the strings as they were printed. None of them have duplicated digits.
Sampling WITHOUT replacement gives 4*3*2*1 = 24 possibilities, exactly as
your code produces.
--
Steven.
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Wed, 2005-07-13 at 11:09 -0400, rbt wrote:
> On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
> > Say I have a list that has 3 letters in it:
> >
> > ['a', 'b', 'c']
> >
> > I want to print all the possible 4 digit combinations of those 3
> > letters:
> >
> > 4^3 = 64
> >
> >
> > abaa
> > aaba
> > aaab
> > acaa
> > aaca
> > aaac
> > ...
> >
> > What is the most efficient way to do this?
>
> Expanding this to 4^4 (256) to test the random.sample function produces
> interesting results. It never finds more than 24 combinations out of the
> possible 256. This leads to the question... how 'random' is sample ;)
>
> Try it for yourselves:
>
> test = list('1234')
>
> combinations = []
> while 1:
> combo = random.sample(test, 4)
> possibility = ''.join(combo)
> if possibility not in combinations:
> print possibility
> combinations.append(possibility)
> continue
> else:
> continue
>
Someone pointed out off-list that this is doing permutation, not
combination. Is there a way to make random.sample to do combinations?
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Wed, 13 Jul 2005 10:39:41 -0400, rbt wrote: >> > What is the most efficient way to do this? >> >> Efficient for who? The user? The programmer? The computer? Efficient use >> of speed or memory or development time? > > The CPU Ah, then that's easy. Sit down with pencil and paper, write out all 64 combinations yourself, and then type them into a Python list. Then you can access any one of those combinations with a single call. A lookup table is the fastest possible way for the CPU to give you the answer you want. [snip] > My list is not arbitrary. I'm looking for all 'combinations' as I > originally posted. Order does not matter to me... just all possibilities. That's good, since you only need combinations of "a", "b" and "c" the lookup table is quite small and manageable. I was worried that you might have wanted to apply your function to any set of items. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Wed, 2005-07-13 at 10:21 -0400, rbt wrote:
> Say I have a list that has 3 letters in it:
>
> ['a', 'b', 'c']
>
> I want to print all the possible 4 digit combinations of those 3
> letters:
>
> 4^3 = 64
>
>
> abaa
> aaba
> aaab
> acaa
> aaca
> aaac
> ...
>
> What is the most efficient way to do this?
Expanding this to 4^4 (256) to test the random.sample function produces
interesting results. It never finds more than 24 combinations out of the
possible 256. This leads to the question... how 'random' is sample ;)
Try it for yourselves:
test = list('1234')
combinations = []
while 1:
combo = random.sample(test, 4)
possibility = ''.join(combo)
if possibility not in combinations:
print possibility
combinations.append(possibility)
continue
else:
continue
--
http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Thu, 2005-07-14 at 00:47 +1000, Steven D'Aprano wrote: > On Wed, 13 Jul 2005 10:21:19 -0400, rbt wrote: > > > Say I have a list that has 3 letters in it: > > > > ['a', 'b', 'c'] > > > > I want to print all the possible 4 digit combinations of those 3 > > letters: > > > > 4^3 = 64 > > > > > > abaa > > aaba > > aaab > > acaa > > aaca > > aaac > > ... > > > > What is the most efficient way to do this? > > Efficient for who? The user? The programmer? The computer? Efficient use > of speed or memory or development time? The CPU > > If you want the fastest runtime efficiency, a lookup table of > pre-calculated values. That is an O(1) operation, and you don't get any > faster than that. > > If you expect to extend the program to arbitrary lists, pre-calculation > isn't practical, so you need an algorithm to calculate permutations (order > matters) or combinations (order doesn't matter). My list is not arbitrary. I'm looking for all 'combinations' as I originally posted. Order does not matter to me... just all possibilities. -- http://mail.python.org/mailman/listinfo/python-list
Re: all possible combinations
On Wed, 13 Jul 2005 10:21:19 -0400, rbt wrote: > Say I have a list that has 3 letters in it: > > ['a', 'b', 'c'] > > I want to print all the possible 4 digit combinations of those 3 > letters: > > 4^3 = 64 > > > abaa > aaba > aaab > acaa > aaca > aaac > ... > > What is the most efficient way to do this? Efficient for who? The user? The programmer? The computer? Efficient use of speed or memory or development time? If you want the fastest runtime efficiency, a lookup table of pre-calculated values. That is an O(1) operation, and you don't get any faster than that. If you expect to extend the program to arbitrary lists, pre-calculation isn't practical, so you need an algorithm to calculate permutations (order matters) or combinations (order doesn't matter). If you tell us what you need, I'm sure somebody will be able to help meet those needs. Otherwise, we're just guessing what you want. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
