[pythonvis] Re: A problem for anyone who wishes to be challenged.

  • From: derek riemer <driemer.riemer@xxxxxxxxx>
  • To: pythonvis@xxxxxxxxxxxxx
  • Date: Sat, 06 Jun 2015 20:40:56 -0600

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.

Other related posts: