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.
