Hi all.
I want to create a large list like:
aaaa ~ zzzz
Is there any good algorithm to do this?
Thanx
Jia Lu 22 1430
On Apr 12, 10:16�pm, "Jia Lu" <Roka...@gmail.comwrote:
Hi all.
*I want to create a large list like:
aaaa ~ zzzz
Is there any good algorithm to do this?
Sure.
test = '01'
for m in test:
for n in test:
for o in test:
for p in test:
print m+n+o+p
## 0000
## 0001
## 0010
## 0011
## 0100
## 0101
## 0110
## 0111
## 1000
## 1001
## 1010
## 1011
## 1100
## 1101
## 1110
## 1111
Now just change test='01' to test='abcdefghijklmnopqrstuvwxyz'.
>
Thanx
Jia Lu
me********@aol.com wrote:
On Apr 12, 10:16�pm, "Jia Lu" <Roka...@gmail.comwrote:
>Hi all. �I want to create a large list like:
aaaa ~ zzzz
Is there any good algorithm to do this?
Sure.
test = '01'
for m in test:
for n in test:
for o in test:
for p in test:
print m+n+o+p
[snip]
Forgive any silly mistakes I have made (I've been teaching
myself python for about 1 week) but there is a moderately
well known algorithm for this that extends to arbitrary
lengths of both the list of alternatives and the length
of the required output, and avoids deeply nested loops.
I know that it is no better for small and constant output
lengths, but for longer lengths or if the output length
can vary it should be better. There is a similar algorithm
if duplicates are not allowed (ie abcd ... wxyz).
My attempt at a python translation of the algorithm:
def m_from_n ( v, m ):
"""
Print all combinations of m things from v[0] ... v[n-1],
duplicates OK. Yields a list.
"""
x = [0] * m
while True:
yield [ v[i] for i in x ]
i = m - 1
while i>=0 and x[i]==len(v)-1:
x[i] = 0
i = i - 1
if i >= 0:
x[i] = x[i] + 1
else:
return
for y in m_from_n( "xyz", 2 ):
print ''.join(y)
xx
xy
xz
yx
yy
yz
zx
zy
zz
for y in m_from_n( [0,1], 3 ):
print y
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
for y in m_from_n( "abcdefghijklmnopqrstuvwxyz", 4 ):
print ''.join(y)
should more or less do what you want.
Charles
Charles Sanders <C.*******************@BoM.GOv.AUwrites:
Forgive any silly mistakes I have made (I've been teaching
myself python for about 1 week) but there is a moderately
well known algorithm for this that extends to arbitrary
lengths of both the list of alternatives and the length
of the required output, and avoids deeply nested loops.
s = "abcd"
def a(n):
if n==0:
yield ''
return
for c in s:
for r in a(n-1):
yield c+r
print list(a(3))
Paul Rubin wrote:
[snip]
>
def a(n):
if n==0:
yield ''
return
for c in s:
for r in a(n-1):
yield c+r
print list(a(3))
Of course, obvious in retrospect, recursion instead of iteration.
I have yet to completely wean myself off Fortran style thinking.
Charles
for m in test:
for n in test:
for o in test:
for p in test:
print m+n+o+p
Thanx for your anwser.
But if I consider about a combination of over 26 letter's list just
like:
"abcdefssdzxcvzxcvzcv"
"asllxcvxcbbedfgdfgdg"
......
Need I write 26 for loops to do this?
Thanx
Jia LU
I think that this would be very silly to do. bad kung foo. The
recoursion technique would be more satisfying. You sholud consider
that this would take about 4 lines to write. Also be avare of the
default recoursion depth in python wich is 1000. you can get and set
the recoursion limit hrough importing the "sys" module and using
getrecoursionlimit() and setrecoursionlimit().
On Apr 13, 9:16 am, "Jia Lu" <Roka...@gmail.comwrote:
for m in test:
for n in test:
for o in test:
for p in test:
print m+n+o+p
Thanx for your anwser.
But if I consider about a combination of over 26 letter's list just
like:
"abcdefssdzxcvzxcvzcv"
"asllxcvxcbbedfgdfgdg"
.....
Need I write 26 for loops to do this?
Thanx
Jia LU
On Apr 13, 8:16 am, "Jia Lu" <Roka...@gmail.comwrote:
for m in test:
for n in test:
for o in test:
for p in test:
print m+n+o+p
Thanx for your anwser.
But if I consider about a combination of over 26 letter's list just
like:
"abcdefssdzxcvzxcvzcv"
"asllxcvxcbbedfgdfgdg"
.....
Need I write 26 for loops to do this?
Thanx
Jia LU
Try this: http://aspn.activestate.com/ASPN/Coo.../Recipe/502199
You could then write something like:
import string
for thiscomb in comb2( *([string.lowercase]*26) ):
...
Mind you, it generates a lot of combinations.
- Paddy.
azrael wrote:
I think that this would be very silly to do. bad kung foo. The
recoursion technique would be more satisfying. You sholud consider
that this would take about 4 lines to write. Also be avare of the
default recoursion depth in python wich is 1000. you can get and set
the recoursion limit hrough importing the "sys" module and using
getrecoursionlimit() and setrecoursionlimit().
Well, you'd have to spell sys.getrecursionlimit() correctly, but yes ;)
At least in the past, raising the recursion limit past a certain point
would result in the CPython interpreter crashing, so it's not completely
scalable.
--
Michael Hoffman
sorry for the bad grammar. I didn't investigate the StackLess Python,
but as I have been reading about it (so if it was correct), the
recursionlimit should not be the problem using StackLess Python.
>From my expirience with python and recursions, it works well to the
depth of about 200 to 500 (depending od algorithm and purpose). I
think that in this case it should work well with about 500. If you
need a bigger string, then lett it repeat and merge the different
strings.
You could also generate multidimensional hash.
Best Regards
On Apr 13, 2:24 pm, Michael Hoffman <cam.ac...@mh391.invalidwrote:
azrael wrote:
I think that this would be very silly to do. bad kung foo. The
recoursion technique would be more satisfying. You sholud consider
that this would take about 4 lines to write. Also be avare of the
default recoursion depth in python wich is 1000. you can get and set
the recoursion limit hrough importing the "sys" module and using
getrecoursionlimit() and setrecoursionlimit().
Well, you'd have to spell sys.getrecursionlimit() correctly, but yes ;)
At least in the past, raising the recursion limit past a certain point
would result in the CPython interpreter crashing, so it's not completely
scalable.
--
Michael Hoffman
Jia Lu wrote:
>for m in test: for n in test: for o in test: for p in test: print m+n+o+p
Thanx for your anwser.
But if I consider about a combination of over 26 letter's list just
like:
"abcdefssdzxcvzxcvzcv"
"asllxcvxcbbedfgdfgdg"
.....
Need I write 26 for loops to do this?
Thanx
Jia LU
Your new example uses 20-byte strings anyway, so to produce those using
the specified method you would need 20 nested for loops, not 26.
I'm pretty sure you could give a separate name to each atom ont he known
universe with a scheme like this. Do you really need 20-byte strings?
regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Recent Ramblings http://holdenweb.blogspot.com
On Apr 13, 8:53 am, Steve Holden <s...@holdenweb.comwrote:
Jia Lu wrote:
for m in test:
for n in test:
for o in test:
for p in test:
print m+n+o+p
Thanx for your anwser.
But if I consider about a combination of over 26 letter's list just
like:
"abcdefssdzxcvzxcvzcv"
"asllxcvxcbbedfgdfgdg"
.....
Need I write 26 for loops to do this?
Thanx
Jia LU
Your new example uses 20-byte strings anyway, so to produce those using
the specified method you would need 20 nested for loops, not 26.
I'm pretty sure you could give a separate name to each atom ont he known
universe with a scheme like this. Do you really need 20-byte strings?
regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Recent Ramblings http://holdenweb.blogspot.com- Hide quoted text -
- Show quoted text -
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
-- Paul
* ref: Project Gutenberg - http://www.gutenberg.org/etext/100 -
unzipped plaintext is ~5.3Mb
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
Oops, you have this formula in math?
Actually I want to scan a range of network for some certain files.
On Apr 13, 9:27 am, "Jia Lu" <Roka...@gmail.comwrote:
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
Oops, you have this formula in math?
Actually I want to scan a range of network for some certain files.
Sorry, Jia Lu, I don't. I was actually just joking, alluding to the
old saying that goes "if you had an infinite number of monkeys typing
randomly on an infinite number of typewriters, they will eventually
type out the works of Shakespeare." "Typewriters"! who uses
typewriters any more?!
-- Paul
On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote:
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
Not likely, even with a tiny sampling of the works of Shakespeare:
# :-)
import string
import random
def main(bardText, maxTries=5000000):
tries = 0
while tries < maxTries:
tries += 1
attempt = []
for letter in bardText.lower():
if random.choice(
string.lowercase[:26]
+ string.punctuation
+ ' '
) == letter:
attempt.append(letter)
else:
break
if len(attempt) >= 4:
print '%d: %s' % (
tries,
''.join(attempt)
)
if __name__ == "__main__":
main("Alas, poor Yorick!")
On Apr 13, 10:22 am, Michael Bentley <mich...@jedimindworks.com>
wrote:
On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote:
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
Not likely, even with a tiny sampling of the works of Shakespeare:
# :-)
import string
import random
def main(bardText, maxTries=5000000):
tries = 0
while tries < maxTries:
tries += 1
attempt = []
for letter in bardText.lower():
if random.choice(
string.lowercase[:26]
+ string.punctuation
+ ' '
) == letter:
attempt.append(letter)
else:
break
if len(attempt) >= 4:
print '%d: %s' % (
tries,
''.join(attempt)
)
if __name__ == "__main__":
main("Alas, poor Yorick!")
5000000 << infinity
Keep tryin'!
Also, the OP's technique was not doing random string permutations, but
generating an exhaustive list of all possible sequences from aaa... to
zzz... . So I think the works of Shakespeare are *bound* to be in
there somewhere.
For proof, here's an extract from my sample code from running this
exhaustive program with length=14:
....
ALASPOORYORICG
ALASPOORYORICH
ALASPOORYORICI
ALASPOORYORICJ
ALASPOORYORICK
ALASPOORYORICL
ALASPOORYORICM
ALASPOORYORICN
ALASPOORYORICO
....
-- Paul
:) (too late for April 1, unfortunately)
On Fri, 2007-04-13 at 10:22 -0500, Michael Bentley wrote:
On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote:
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
Not likely, even with a tiny sampling of the works of Shakespeare:
Actually, the OP seems to be interested in generating *all* strings of
length N. If you generate the set of *all* strings of 5 million
characters length, at least one of them will contain all works of
Shakespeare. That statement is utterly true and utterly impractical,
which is, of course, the point of Paul's joke.
-Carsten
On Apr 13, 10:49 am, Carsten Haese <cars...@uniqsys.comwrote:
On Fri, 2007-04-13 at 10:22 -0500, Michael Bentley wrote:
On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote:
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
Not likely, even with a tiny sampling of the works of Shakespeare:
Actually, the OP seems to be interested in generating *all* strings of
length N. If you generate the set of *all* strings of 5 million
characters length, at least one of them will contain all works of
Shakespeare. That statement is utterly true and utterly impractical,
which is, of course, the point of Paul's joke.
-Carsten
But even random typing will *eventually* get there (where "eventually"
= several gazillion times the age of the universe) - see http://en.wikipedia.org/wiki/Infinite_monkey_theorem.
-- Paul
If I see farther, it is because I stand on the shoulders of an
infinite number of monkeys.
On Apr 13, 8:53 am, Steve Holden <s...@holdenweb.comwrote:
>
I'm pretty sure you could give a separate name to each atom ont he known
universe with a scheme like this. Do you really need 20-byte strings?
Steve,
Based on the Wikipedia article's estimate of 10**79 atoms in the
observable universe (is that all?), we would need a string of about 57
characters long to give each one a separate name.
(And I'll bet you've typed on an old Royal or two in your time...)
-- Paul
On Apr 13, 10:41 am, "Paul McGuire" <p...@austin.rr.comwrote:
On Apr 13, 10:22 am, Michael Bentley <mich...@jedimindworks.com>
wrote:
On Apr 13, 2007, at 9:19 AM, Paul McGuire wrote:
If you just expand the length to five million* or so, one of those
strings will contain all the works of Shakespeare.
Not likely, even with a tiny sampling of the works of Shakespeare:
# :-)
import string
import random
def main(bardText, maxTries=5000000):
tries = 0
while tries < maxTries:
tries += 1
attempt = []
for letter in bardText.lower():
if random.choice(
string.lowercase[:26]
+ string.punctuation
+ ' '
) == letter:
attempt.append(letter)
else:
break
if len(attempt) >= 4:
print '%d: %s' % (
tries,
''.join(attempt)
)
if __name__ == "__main__":
main("Alas, poor Yorick!")
5000000 << infinity
Keep tryin'!
Also, the OP's technique was not doing random string permutations, but
generating an exhaustive list of all possible sequences from aaa... to
zzz... . So I think the works of Shakespeare are *bound* to be in
there somewhere.
For proof, here's an extract from my sample code from running this
exhaustive program with length=14:
...
ALASPOORYORICG
ALASPOORYORICH
ALASPOORYORICI
ALASPOORYORICJ
ALASPOORYORICK
ALASPOORYORICL
ALASPOORYORICM
ALASPOORYORICN
ALASPOORYORICO
...
-- Paul
:) (too late for April 1, unfortunately)- Hide quoted text -
- Show quoted text -
And apologies to the OP for beating a dead horse into the ground.
-- Paul
Paul McGuire wrote:
On Apr 13, 8:53 am, Steve Holden <s...@holdenweb.comwrote:
>I'm pretty sure you could give a separate name to each atom ont he known universe with a scheme like this. Do you really need 20-byte strings?
Steve,
Based on the Wikipedia article's estimate of 10**79 atoms in the
observable universe (is that all?), we would need a string of about 57
characters long to give each one a separate name.
>>10 ** 79 26 ** 20
True
>>>
Well, we can't be right all the time, I suppose. Perhaps I need to
raise my certainty filters.
(And I'll bet you've typed on an old Royal or two in your time...)
Who are you calling a monkey?
look-out-for-my-infinite-number-of-friends-ly y'rs - steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Recent Ramblings http://holdenweb.blogspot.com
Are you maybe trying to create a rainbow table, or a very big
dictionary
Paul McGuire wrote:
If I see farther, it is because I stand on the shoulders of an
infinite number of monkeys.
If I ever get around to writing a book on numerical methods/computational
science/whatever, this will be the chapter quote for my chapter on Monte Carlo
algorithms.
--
Robert Kern
"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: cody |
last post by:
I have to write an algorithm with must ensure that objects are put in
buckets (which are always 4 in size).
The objects have two properties: A and B. It is not allowed that in a bucket
are objects...
|
by: Jerry Khoo |
last post by:
My problem is this:
i am currently in taking OS course, and my lecturer would like us to
find ways to construct a CPU algorithm such as SJF(shortest Job
First), SRTF (Shortest Remaining Time...
|
by: Peter Olcott |
last post by:
www.halting-problem.com
|
by: FBM |
last post by:
Hi,
I am working on a program that simulates one of the elements of ATM.
The simulation stores events which occurs every some milliseconds for a
certain amount of time. Every time that an event...
|
by: Bo Yang |
last post by:
Hi ,
I have writen a python program to slove a problem described as below:
(Forgive my poor English !)
Put the 2^n 0 or 1 to form a ring , and we can select any continuous n
ones from
the...
|
by: Sherrie Laraurens |
last post by:
Hi all,
I'm trying to write a generic algorithm routine that will
take begin and end iterators of a container, iterate through
the range and perform a "calculation" of sorts.
The trouble is...
|
by: jamesonang |
last post by:
Supposed unsigned int(32 bits) is the largest number that computer can
represent with a single variable.
Now, i have a big integer ( less than 64 bit, but great than 32 bit) .
i represent it by...
|
by: Sunway |
last post by:
hello guys i have a bunsh of questions in java and algorithm
most of them i didnt have a problem in them but two i had a diffculty in them could u help me in them please coz its urgent .
the...
|
by: James Dow Allen |
last post by:
On May 7, 11:24 pm, sophia <sophia.ag...@gmail.comwrote:
Contrary to a suggestion in this thread,
the straightforward solution to this puzzle
is not of exponential complexity, but rather N^3/3....
|
by: VictorG |
last post by:
Hello,
I am trying to secure a webservice using WSE 3.0 and the turnkey
usernameForCertificateSecurity profile. I am passing a valid username
token, and on the server I have overridden the...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |