Hi Derek,
I might be up to the challenge, but after a few days. However, I would
like to ask you or whoever knows about a good set of materials on
algorithms. There are lots of materials on the net, but most of them are
pdf files or use images to show key parts of the logic and trying to
decode the missing parts can be rather frustrating.
TIA,
Dzhovani
On 8.6.2015 г. 20:16 ч., derek riemer wrote:
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.
