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:
1printAllPermutations(1)
1 2printAllPermutations(2)
1 2 3printAllPermutations(3))
1 2 3d=yieldPermutation(3)
next(d)
1 3 2next(d)
3 1 2next(d)
2 1 3next(d)
2 3 1next(d)
3 2 1next(d)
Traceback (most recent call last):next(d)