Hi,
I also have solution but it is rather slow, mainly because it's
recursive, I suppose. I'd be glad to see the fast solutions.
Regards,
Dzhovani
PS: I'm pasting the code below as well.
#this is the main function that makes the permutations
def perm(seq, i):
if i == len(seq):
print seq
else:
for j in range(i, len(seq)):
seq[i], seq[j] = seq[j], seq[i]
perm(seq, i+1)
seq[i], seq[j] = seq[j], seq[i]
# end of the for statement
# end of the if statement
# end of the function
#this function takes N, generates a list to be permutated and passes it
to the function above
def main_perms(n):
seq =[x for x in range(1, n +1)]
perm(seq, 0)
# example with N = 4
main_perms(4)
On 19.6.2015 г. 01:33 ч., Richard Dinger wrote:
OK, I have an answer and it takes 15 seconds to permute range(10). I
will hold off for now and wait for others. I say time is proportional
to n! (factorial)
You asked why 11 is the upper limit -- it isn't if you use hex instead
of decimal.
-----Original Message----- From: derek riemer
Sent: Monday, June 08, 2015 10:16 AM
To: pythonvis@xxxxxxxxxxxxx
Subject: [pythonvis] Re: A problem for anyone who wishes to be
challenged.
Correct. I didn't know that existed in itertools. It just goes to show
how dang rich the python stl is. nevertheless, it is still a very fun
problem and I will keep it open.
On 6/6/2015 9:52 PM, Richard Dinger wrote:
I say leave it open for a while yet. I have not listened in detail
yet to your description. My first impression is that you want to
calculate permutations without simply using the generator in the
itertools module. Is that correct?
-----Original Message----- From: derek riemer
Sent: Saturday, June 06, 2015 7:40 PM
To: pythonvis@xxxxxxxxxxxxx
Subject: [pythonvis] Re: A problem for anyone who wishes to be
challenged.
Would anyone like an answer? If not, I will just leave it open.
On 6/1/2015 10:55 PM, Joseph Lee wrote:
Hi Derek,
Ah, a very interesting challenge.
For anyone willing to do it, try working out how permutations are
printed, then work with each entry (1, 2, 3, etc.).
For those wanting to go into running time of algorithms (worse case,
that's what Big O means), two wrong answers are linear and
polynomial. If it is linear or polynomial, Python would not have a
hard time working on it in reasonable time.
Cheers,
Joseph
-----Original Message-----
From: pythonvis-bounce@xxxxxxxxxxxxx
[mailto:pythonvis-bounce@xxxxxxxxxxxxx] On Behalf Of derek riemer
Sent: Monday, June 1, 2015 9:46 PM
To: pythonvis@xxxxxxxxxxxxx
Subject: [pythonvis] A problem for anyone who wishes to be challenged.
Hi guys,
I was playing with this, and a solution exists but can't run verry
fast.
My solution can generate numbers up to 10 successfully.
I also wrote the program A. in c++ and it still was utterly slow.
In fact I derived a big-o notation for this problem and if anyone is
interested I can post that.
Write 2 programs that:
a. Prints all permutations of the numbers 1 through n, inclusive.
b. yields the numbers. Each time you call it, it needs to give you
another permutation. When it runs out, raise stopIteration.
Here is an interface.
def print_all_permutations(n):
def yieldPermutation(n):
example:
>>> printAllPermutations(1)
1
>>> printAllPermutations(2)
1 2
2 1
>>> printAllPermutations(3))
1 2 3
1 3 2
2 3 1
3 1 2
3 2 1
2 1 3
I mixed them up, my program prints them in a certain order but I
don't want to give away the awesomeness of the problem.
>>> d=yieldPermutation(3)
>>>next(d)
1 2 3
>>>next(d)
1 3 2
>>>next(d)
3 1 2
>>>next(d)
2 1 3
>>>next(d)
2 3 1
>>>next(d)
3 2 1
>>>next(d)
Traceback (most recent call last):
File "mygenerate_numbers.py" line 1, in <module> StopIteration
This would crash for numbers like 11, can you guess why?
This should be considered an advanced problem. In fact I decided to
tackle it to study for my algorithms quiz last semester.
I will give a hint. There is both a recursive and non-recursive
solution to this.
Good luck,
Derek
List web page is
//www.freelists.org/webpage/pythonvis
To unsubscribe, send email to
pythonvis-request@xxxxxxxxxxxxx with "unsubscribe" in the Subject
field.
List web page is
//www.freelists.org/webpage/pythonvis
To unsubscribe, send email to
pythonvis-request@xxxxxxxxxxxxx with "unsubscribe" in the Subject
field.
List web page is
//www.freelists.org/webpage/pythonvis
To unsubscribe, send email to
pythonvis-request@xxxxxxxxxxxxx with "unsubscribe" in the Subject field.
List web page is //www.freelists.org/webpage/pythonvis
To unsubscribe, send email to pythonvis-request@xxxxxxxxxxxxx with
"unsubscribe" in the Subject field.
List web page is
//www.freelists.org/webpage/pythonvis
To unsubscribe, send email to
pythonvis-request@xxxxxxxxxxxxx with "unsubscribe" in the Subject field.
List web page is //www.freelists.org/webpage/pythonvis
To unsubscribe, send email to pythonvis-request@xxxxxxxxxxxxx with
"unsubscribe" in the Subject field.
