How to approach difficult problems?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

How to approach difficult problems?

Postby luke77 » Thu Oct 09, 2008 11:23 pm UTC

Hi guys,

This is a bit of an obscure question, but I'm a beginning programmer and I'm wondering if there is a "systematic" way to approach problems you are just stumped with. For instance, I'm working my way through Project Euler, and I'm currently stumped with Problem 24:

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?



I've tried various things and have a general idea how it should be solved, but I'm just not getting it. Iteration is probably not a correct approach because of the magnitude of the numbers needed. I think the solution requires some sort of recursive approach, removing the first digit and then calling the function with the remaining digits, but I can't get the proram to do this and consider options where the "0" is not the first number in the permutation (eg 1023456789).

More generally, though, is there a method to approach problems that you can't solve, rather than just "thinking about it" for a while? Is there a stepwise approach?

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: How to approach difficult problems?

Postby spdqbr » Fri Oct 10, 2008 12:09 am UTC

Recursion is generally very good for permutations, so you're on the right track. In general, with PE problems, I tend to write out a few cases by hand, and then see if I can figure out how I did it. That is, most of the time I will write out the result of my own intuitive algorithm and then see if there's a way to code that.

For permutations in lexicographic order I would write out by hand how I would do 3 or 4 elements. Then try to figure out the method behind it.

Though with later PE problems, the intuitive method is too slow, so you have to get clever (I'm not).

That may not be much help, but it's the best I can offer. Also, interestingly enough I lost all of my PE solutions a while ago, so I've been going through this and writing them again in Java, Python, and Perl (just learning perl). It's frightful good practice, and I've got some of the guys at work doing it too. I've got 1-27 done in all languages so far. It's very confusing switching languages.
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.

Galileo

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How to approach difficult problems?

Postby Xanthir » Fri Oct 10, 2008 12:18 am UTC

spdqbr wrote:Also, interestingly enough I lost all of my PE solutions a while ago, so I've been going through this and writing them again in Java, Python, and Perl (just learning perl). It's frightful good practice, and I've got some of the guys at work doing it too. I've got 1-27 done in all languages so far. It's very confusing switching languages.

Man, seriously. My lisp skills had gotten rusty from lack of practice, but PE has sharpened them to a finer edge than they've ever had.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: How to approach difficult problems?

Postby headprogrammingczar » Fri Oct 10, 2008 1:17 am UTC

In nearly any algorithm, working backwards helps a lot (hint hint).
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: How to approach difficult problems?

Postby Berengal » Fri Oct 10, 2008 1:35 am UTC

To solve complex problems, break it into simple ones and solve them instead. Often, finding an easily solvable sub-problem of the problem, and generalizing from that works well.
For problem 24, ask yourself this:
- How many permutations of the list of digits from 0 to 9 are there?
- The list of permutations is sorted. How many permutations do I have to go through before 0 isn't the first digit?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

jimrandomh
Posts: 110
Joined: Sat Feb 09, 2008 7:03 am UTC
Contact:

Re: How to approach difficult problems?

Postby jimrandomh » Fri Oct 10, 2008 5:06 am UTC

Project Euler is a collection of math problems with a little programming thrown in. The techniques you use to solve them are almost nothing like the techniques you use for real programming. Math is about finding the key insight that lets you reduce a hard problem to one or more easy problems. In programming, decomposing the problem is easy; the difficulty is in keeping the interactions between the parts you've decomposed it into manageable.

Porges
Posts: 46
Joined: Mon Aug 06, 2007 3:01 am UTC
Location: Wellington, New Zealand
Contact:

Re: How to approach difficult problems?

Postby Porges » Fri Oct 10, 2008 7:54 am UTC

How to approach difficult problems? WITH HASKELL!

Mzyxptlk
Posts: 513
Joined: Tue Sep 23, 2008 8:41 am UTC

Re: How to approach difficult problems?

Postby Mzyxptlk » Fri Oct 10, 2008 8:51 am UTC

Sledge hammer first, brains later.


P.S. Don't misread the above statement as "Sledge hammer first... ok, done, next problem".
"Once upon a time, an infinite number of people lived perfect, blissful, eternal lives."

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: How to approach difficult problems?

Postby Dongorath » Fri Oct 10, 2008 10:13 am UTC

Here how I try to solve PE problems :
  1. Bruteforce !!! Try all the parameters space and check each one for the property. Will work on early problems. Eg : on problem 5, for each number starting from 1, check if it's evenly divisible by all numbers from 1 to 20.
  2. Try to reduce the parameters space as much as possible. Eg : on problem five, notice that it must be evenly divisible by 2, so you only have to check even numbers, and it must be envenly divisible by 20, so you can start at 20.
  3. Try to optimize the tests. Eg : on problem 5, don't check that (n/p)*p == n (where '/' is the integer division) but check that n % p == 0.
  4. Headdesk !!!
  5. Have a revelation and write the one-liner needed to solve efficiently the problem. Eg : on problem 5, it's in fact finding the lowest common multiple (lcm) of the integers 2 to 20.
  6. Try to optimize the new algorithm (reduction of parameters space and reduce complexity of tests).
  7. Headdesk !!!
  8. ...
  9. Profit !

Sometimes, even if you don't have the clever solution which derive from lots of previous calculations on paper, optimized calculations might save you (meoization, precalculation, generators, etc.). But always use pen and paper before trying to bruteforce, it's really usefull and more satisfying. And once solve, see how the other have done, you might learn a few things.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: How to approach difficult problems?

Postby You, sir, name? » Fri Oct 10, 2008 12:56 pm UTC

spdqbr wrote:Recursion is generally very good for permutations, so you're on the right track. In general, with PE problems, I tend to write out a few cases by hand, and then see if I can figure out how I did it. That is, most of the time I will write out the result of my own intuitive algorithm and then see if there's a way to code that.


Adding to that, memoization typically makes recursion even faster.

Porges wrote:How to approach difficult problems? WITH PROLOG!


I fixed it for you. Though, that may be cheating.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

User avatar
segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

Re: How to approach difficult problems?

Postby segmentation fault » Fri Oct 10, 2008 4:08 pm UTC

recursion sounds about right. you can rule out alot of possibilities by figuring out how many permutations there are starting with a certain number. in other words, how many permutations start with 0? we will call this number x. find out 1000000/x and you can get a starting point.

do the same thing for the next number (recursively) only with 1000000 - (1000000 mod x) and so on.

does this make sense or am i just pretending to be smart?

so maybe the 1000000 - (1000000 mod x) doesnt make sense (im still trying to figure out wha tto call it with recursively) but if anyone can check my answer then i will have already figured it out:

Spoiler:
1562403789
people are like LDL cholesterol for the internet

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: How to approach difficult problems?

Postby luke77 » Sat Oct 11, 2008 4:55 pm UTC

OK, I still can't figure out 24 on Euler. If anyone else has done it or knows how to write a recursive function to solve it, cuold you please share?

Thanks

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: How to approach difficult problems?

Postby jaap » Sat Oct 11, 2008 6:04 pm UTC

luke77 wrote:OK, I still can't figure out 24 on Euler. If anyone else has done it or knows how to write a recursive function to solve it, could you please share?


No, that's not the done thing. What exactly is it that you can't figure out? Can you answer the two hint questions that Berengal asked?
Berengal wrote:- How many permutations of the list of digits from 0 to 9 are there?
- The list of permutations is sorted. How many permutations do I have to go through before 0 isn't the first digit?

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: How to approach difficult problems?

Postby luke77 » Sat Oct 11, 2008 7:02 pm UTC

jaap wrote:
luke77 wrote:OK, I still can't figure out 24 on Euler. If anyone else has done it or knows how to write a recursive function to solve it, could you please share?


No, that's not the done thing. What exactly is it that you can't figure out? Can you answer the two hint questions that Berengal asked?
Berengal wrote:- How many permutations of the list of digits from 0 to 9 are there?
- The list of permutations is sorted. How many permutations do I have to go through before 0 isn't the first digit?


Well, I'm trying to find the answer but more importantly, I'm trying to figure out how to recursively print all of the possible permutations (as an exercise, since I can't figure out how to do this). To answer the questions, though:

1: For the list of [0], there is 1 permutation (1!)
For the list of digits from 0 to 1, there are 2 permutations (2!)
For the list of digits from 0 to 2, there are 6 permutations (3!)

Therefore, (I think) for the list from 0 to 9, there are 10! possible permutations.

2: I'm not quite sure what "The list of permutations is sorted" means, since I don't have the list yet. Assuming I do have a list, though, you have to go through 10!/10 or 9! digits to get to the first permutation where 0 is not the first digit. I'm sure that I could figure the answer out mathematically, on paper, just based on this information and narrowing it down, but I'd really like to be able to figure it out using a recursive function in python, since my real objective is to teach myself python and not just get an answer. What I'm struggling with is writing a function that will generate possible permutations, so that I could enter, for instance, f(10000) and it would return the 10,000th possible permutation.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: How to approach difficult problems?

Postby jaap » Sat Oct 11, 2008 9:07 pm UTC

luke77 wrote:Therefore, (I think) for the list from 0 to 9, there are 10! possible permutations.


Correct.

luke77 wrote:2: I'm not quite sure what "The list of permutations is sorted" means, since I don't have the list yet.

luke77 wrote:What I'm struggling with is writing a function that will generate possible permutations, so that I could enter, for instance, f(10000) and it would return the 10,000th possible permutation.


Are you really thinking of generating the whole list one by one, until you get to the 10000th one? That is an interesting task too, but you don't need it for this problem. You can calculate what the permutation must be from the number directly. And once you can do that, of course you can easily generate the list too with a simple loop.

luke77 wrote:Assuming I do have a list, though, you have to go through 10!/10 or 9! digits to get to the first permutation where 0 is not the first digit.


If you were given the index number on this list of one of the permutations, you should therefore be able to work out what the first digit of the permutation should be. This leaves you with a smaller problem to solve, namely working out what the next 9 digits of the permutation are. That smaller problem can be solved in almost exactly the same way, hence recursion.

luke77 wrote: I'm sure that I could figure the answer out mathematically, on paper, just based on this information and narrowing it down, but I'd really like to be able to figure it out using a recursive function in python, since my real objective is to teach myself python and not just get an answer.


I don't know any Python, but you can't write a recursive function if you don't even have a strategy for working out what it is going to do. With PE problems it very often takes much more time to figure out the solving strategy or algorithm you should use than the actual programming and debugging.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: How to approach difficult problems?

Postby Berengal » Sat Oct 11, 2008 9:31 pm UTC

I solved problem 24 by hand (and python, but only for punching numbers). It was faster than writing up the code to do it for me. What took time was figuring out how to do it...
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

pma
Posts: 4
Joined: Sat Sep 27, 2008 8:17 pm UTC

Re: How to approach difficult problems?

Postby pma » Sat Oct 11, 2008 11:09 pm UTC

My not-ideal-but-good-enough solution:
Spoiler:

Code: Select all

(define (fac n)
  (cond
    ((= n 0) 1)
    (else (faci n 1 1))))
(define (faci n i a)
  (cond
    ((= n i) (* i a))
    (else (faci n (1+ i) (* i a)))))
(define (pick n ln)
  (cond
    ((= n 1) (car ln))
    (else (pick (1- n) (cdr ln)))))
(define (remnth n ln)
  (cond
    ((= n 1) (cdr ln))
    (else (cons (car ln) (remnth (1- n) (cdr ln))))))
(define (nthpermhelp nth often ln)
  (cond
    ((= often 0) (car ln))
    (else (let* ((fact (fac often)) (ceil (ceiling (/ nth fact))))
            (+ (* (expt 10 often)
                  (pick ceil ln))
               (nthpermhelp (- nth
                               (* fact (1- ceil)))
                            (1- often)
                            (remnth ceil ln)))))))
(define (nthperm n ln)
  (nthpermhelp n (1- (length ln)) ln))

chibu
Posts: 15
Joined: Sat Oct 11, 2008 4:38 pm UTC

Re: How to approach difficult problems?

Postby chibu » Sun Oct 12, 2008 11:40 am UTC

I actually solved this problem accidentally. I happened to have the code lying around from my senior project for graduating from college which was about finding determinants of huge matrices. The entries were based on the points in a given Permutohedron. As such, I already had to have an efficient algorithm.

But, yes, it is written recursively. You need to be careful with Python though. It doesn't like it when you recurse too much (there's probably a config setting to change that? I never got around to looking though).

In the Spoiler, I will explain a basic algorithm for generating the next permutation in lexicographical order. I am not giving code, but explaining the concept of how one might try to code it. So, if this is what you're looking for, feel free to look. But, since it explains it in detail, it may still be a spoiler. Since you seem to be trying to do this to learn how to program, I think it should be fine as you'll still have to do all of the actual programming.

Spoiler:
If you're looking for help on how to generate lexicographical permutations, like everyone else said, you need to look at how you do it by hand:

0 -> 1 2 3 4
1 -> 1 2 4 3
2 -> 1 3 2 4
3 -> 1 3 4 2
4 -> 1 4 2 3
5 -> 1 4 3 2
6 -> 2 1 3 4 ...

So, it looks like what we're doing here is swapping two values, over and over. But, that's a little bit misleading because we're looking at a small list.

The first thing that we look for is the last (right-most) entry in which the entry after it is larger. If are list is called L we're looking for the highest value of i such that L[i] < L[i+1].

Once we have that established, we will swap the value at i withe the smallest value after it in the list which is also larger than L[i].

Finally, we will want to reverse all of the values that are now after position i in the list. This will have the effect of making the elements after i in the list be in ascending order.

That's it. We then return our value, or store it in an array, and run the algorithm again to find the next value.

-------------------------------

Now that we have a description of the algorithm, we are going to look at an example of a larger set. Let's say, 7 elements: 1 2 3 4 5 6 7. But, since it's easier to see what happens with anything other than the first permutation, we'll start with 2 3 4 1 7 6 5.

Code: Select all

So,
  L = [2, 3, 4, 1, 7, 6, 5]
  and [0, 1, 2, 3, 4, 5, 6] are the values of i at each position in the list.

Step 1: Find Largest i where L[i] < {i+1]
   By looking at the list we can see that this is when i = 3.
   That is, the entry of 1 in the list L.

Step 2: Find smallest value after L[i] that is LARGER than L[i]
   Out of the values 7, 6, and 5; We as humans know immediately the answer is 5.
   However, the program will obviously have to compare each value to the others.
   Actually, I might be wrong... But I believe that it will ALWAYS be the LAST value...
   So, you could probably save some time by swapping value at i with the last position.

   Anyway, we now have: L = [2, 3, 4, 5, 7, 6, 1] with 5 now being at position i.

Step 3: Reverse all elements AFTER position i
   Python probably has a reverse array function... if not write one.
   The reverse of the elements 7, 6, 1 is 1, 6, 7.
   Therefore: L = [2, 3, 4, 5, 1, 6, 7]

And that's all. We now return our list which now contains the next permutation in lexicographical order, or write it to an array if we want to save it. We can then send the value to our function again if we want.


So, while this is in fact something of a brute-force method of solving the actual problem, it will still be a good programming exercise for learning python. Running this algorithm only a million times shouldn't take much time at all. especially if you can find some shortcuts to make it more efficient.


Well, I hope that this has been some help to you, if you have any more questions, always feel free to ask.

~ Chibu
Last edited by chibu on Mon Oct 13, 2008 1:14 am UTC, edited 2 times in total.

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: How to approach difficult problems?

Postby luke77 » Mon Oct 13, 2008 12:18 am UTC

This makes perfect sense, and thanks for explaining.

BUT, when I write an algorithm to simulate your method, it seems to break down. Here's the output from my algorithm, starting with the set range(0,10):

[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
[0, 1, 2, 3, 4, 5, 6, 8, 9, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
etc.

As you can see, it repeats indefinitely, although I can't find anywhere where it disobeys the "rules" you set up. With each iteration, the rightmost number where i<i+1 is swapped with the smallest remaining number, and then the list after i is reversed. I feel like I must be missing something basic, but I can't tell where it is.

chibu
Posts: 15
Joined: Sat Oct 11, 2008 4:38 pm UTC

Re: How to approach difficult problems?

Postby chibu » Mon Oct 13, 2008 12:39 am UTC

Edit (again...):
I apologize... I seem to have made a disastrous brain-not-working error. I left out a critical part... >_< You swap the value at i with the smallest value after it that is LARGER than the value at i...

So, the reason it starts repeating is becuase it swaps the 8 with the 7, but it should obviously swap it with the 9. I am very sorry... I can't believe I didn't say that... I went back and folowed my directions like a hundred times and couldn't figure it out... The example I used makes that particular point not matter, as the value at i is 1...

*sigh* Well, I hope it will work for you now. I'm going to go edit the other post to show the correct process.

Good Luck, and again, sorry about that,

~ Chibu

luke77
Posts: 47
Joined: Fri Oct 03, 2008 4:54 pm UTC

Re: How to approach difficult problems?

Postby luke77 » Mon Oct 13, 2008 2:16 am UTC

That's what I was thinking, and when I made that adjustment things look better, but still not correct. Below are the first hundred permutations using the modified algorithm. We run into trouble when there is no value after i that is greater than the value at i; for instance, [0, 1, 2, 9, 8, 7, 6, 5, 4, 3] becomes [0, 1, 9, 3, 4, 5, 6, 7, 8, 2] using the modified algorithm because there is no value after 2 that is greater than 2, so the program uses the maximum value. In these special cases, should I be substituting the MINIMUM value after i?

[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
[0, 1, 2, 3, 4, 5, 9, 7, 8, 6]
[0, 1, 2, 3, 4, 5, 9, 8, 6, 7]
[0, 1, 2, 3, 4, 5, 9, 8, 7, 6]
[0, 1, 2, 3, 4, 9, 6, 7, 8, 5]
[0, 1, 2, 3, 4, 9, 6, 8, 5, 7]
[0, 1, 2, 3, 4, 9, 6, 8, 7, 5]
[0, 1, 2, 3, 4, 9, 8, 5, 7, 6]
[0, 1, 2, 3, 4, 9, 8, 7, 6, 5]
[0, 1, 2, 3, 9, 5, 6, 7, 8, 4]
[0, 1, 2, 3, 9, 5, 6, 8, 4, 7]
[0, 1, 2, 3, 9, 5, 6, 8, 7, 4]
[0, 1, 2, 3, 9, 5, 8, 4, 7, 6]
[0, 1, 2, 3, 9, 5, 8, 7, 6, 4]
[0, 1, 2, 3, 9, 8, 4, 6, 7, 5]
[0, 1, 2, 3, 9, 8, 4, 7, 5, 6]
[0, 1, 2, 3, 9, 8, 4, 7, 6, 5]
[0, 1, 2, 3, 9, 8, 7, 5, 6, 4]
[0, 1, 2, 3, 9, 8, 7, 6, 4, 5]
[0, 1, 2, 3, 9, 8, 7, 6, 5, 4]
[0, 1, 2, 9, 4, 5, 6, 7, 8, 3]
[0, 1, 2, 9, 4, 5, 6, 8, 3, 7]
[0, 1, 2, 9, 4, 5, 6, 8, 7, 3]
[0, 1, 2, 9, 4, 5, 8, 3, 7, 6]
[0, 1, 2, 9, 4, 5, 8, 7, 6, 3]
[0, 1, 2, 9, 4, 8, 3, 6, 7, 5]
[0, 1, 2, 9, 4, 8, 3, 7, 5, 6]
[0, 1, 2, 9, 4, 8, 3, 7, 6, 5]
[0, 1, 2, 9, 4, 8, 7, 5, 6, 3]
[0, 1, 2, 9, 4, 8, 7, 6, 3, 5]
[0, 1, 2, 9, 4, 8, 7, 6, 5, 3]
[0, 1, 2, 9, 8, 3, 5, 6, 7, 4]
[0, 1, 2, 9, 8, 3, 5, 7, 4, 6]
[0, 1, 2, 9, 8, 3, 5, 7, 6, 4]
[0, 1, 2, 9, 8, 3, 7, 4, 6, 5]
[0, 1, 2, 9, 8, 3, 7, 6, 5, 4]
[0, 1, 2, 9, 8, 7, 4, 5, 6, 3]
[0, 1, 2, 9, 8, 7, 4, 6, 3, 5]
[0, 1, 2, 9, 8, 7, 4, 6, 5, 3]
[0, 1, 2, 9, 8, 7, 6, 3, 5, 4]
[0, 1, 2, 9, 8, 7, 6, 5, 4, 3]
[0, 1, 9, 3, 4, 5, 6, 7, 8, 2]
[0, 1, 9, 3, 4, 5, 6, 8, 2, 7]
[0, 1, 9, 3, 4, 5, 6, 8, 7, 2]
[0, 1, 9, 3, 4, 5, 8, 2, 7, 6]
[0, 1, 9, 3, 4, 5, 8, 7, 6, 2]
[0, 1, 9, 3, 4, 8, 2, 6, 7, 5]
[0, 1, 9, 3, 4, 8, 2, 7, 5, 6]
[0, 1, 9, 3, 4, 8, 2, 7, 6, 5]
[0, 1, 9, 3, 4, 8, 7, 5, 6, 2]
[0, 1, 9, 3, 4, 8, 7, 6, 2, 5]
[0, 1, 9, 3, 4, 8, 7, 6, 5, 2]
[0, 1, 9, 3, 8, 2, 5, 6, 7, 4]
[0, 1, 9, 3, 8, 2, 5, 7, 4, 6]
[0, 1, 9, 3, 8, 2, 5, 7, 6, 4]
[0, 1, 9, 3, 8, 2, 7, 4, 6, 5]
[0, 1, 9, 3, 8, 2, 7, 6, 5, 4]
[0, 1, 9, 3, 8, 7, 4, 5, 6, 2]
[0, 1, 9, 3, 8, 7, 4, 6, 2, 5]
[0, 1, 9, 3, 8, 7, 4, 6, 5, 2]
[0, 1, 9, 3, 8, 7, 6, 2, 5, 4]
[0, 1, 9, 3, 8, 7, 6, 5, 4, 2]
[0, 1, 9, 8, 2, 4, 5, 6, 7, 3]
[0, 1, 9, 8, 2, 4, 5, 7, 3, 6]
[0, 1, 9, 8, 2, 4, 5, 7, 6, 3]
[0, 1, 9, 8, 2, 4, 7, 3, 6, 5]
[0, 1, 9, 8, 2, 4, 7, 6, 5, 3]
[0, 1, 9, 8, 2, 7, 3, 5, 6, 4]
[0, 1, 9, 8, 2, 7, 3, 6, 4, 5]
[0, 1, 9, 8, 2, 7, 3, 6, 5, 4]
[0, 1, 9, 8, 2, 7, 6, 4, 5, 3]
[0, 1, 9, 8, 2, 7, 6, 5, 3, 4]
[0, 1, 9, 8, 2, 7, 6, 5, 4, 3]
[0, 1, 9, 8, 7, 3, 4, 5, 6, 2]
[0, 1, 9, 8, 7, 3, 4, 6, 2, 5]
[0, 1, 9, 8, 7, 3, 4, 6, 5, 2]
[0, 1, 9, 8, 7, 3, 6, 2, 5, 4]
[0, 1, 9, 8, 7, 3, 6, 5, 4, 2]
[0, 1, 9, 8, 7, 6, 2, 4, 5, 3]
[0, 1, 9, 8, 7, 6, 2, 5, 3, 4]
[0, 1, 9, 8, 7, 6, 2, 5, 4, 3]
[0, 1, 9, 8, 7, 6, 5, 3, 4, 2]
[0, 1, 9, 8, 7, 6, 5, 4, 2, 3]
[0, 1, 9, 8, 7, 6, 5, 4, 3, 2]
[0, 9, 2, 3, 4, 5, 6, 7, 8, 1]
[0, 9, 2, 3, 4, 5, 6, 8, 1, 7]
[0, 9, 2, 3, 4, 5, 6, 8, 7, 1]
[0, 9, 2, 3, 4, 5, 8, 1, 7, 6]
[0, 9, 2, 3, 4, 5, 8, 7, 6, 1]
[0, 9, 2, 3, 4, 8, 1, 6, 7, 5]
[0, 9, 2, 3, 4, 8, 1, 7, 5, 6]
[0, 9, 2, 3, 4, 8, 1, 7, 6, 5]
[0, 9, 2, 3, 4, 8, 7, 5, 6, 1]
[0, 9, 2, 3, 4, 8, 7, 6, 1, 5]
[0, 9, 2, 3, 4, 8, 7, 6, 5, 1]
[0, 9, 2, 3, 8, 1, 5, 6, 7, 4]
[0, 9, 2, 3, 8, 1, 5, 7, 4, 6]
[0, 9, 2, 3, 8, 1, 5, 7, 6, 4]
[0, 9, 2, 3, 8, 1, 7, 4, 6, 5]
[0, 9, 2, 3, 8, 1, 7, 4, 6, 5]

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: How to approach difficult problems?

Postby jaap » Mon Oct 13, 2008 7:06 am UTC

I haven't looked at Chibu's description in detail, but here is one spot in your list that goes wrong:
[0, 1, 2, 9, 4, 5, 6, 8, 7, 3]
[0, 1, 2, 9, 4, 5, 8, 3, 6, 7]

The next one should have been
[0, 1, 2, 9, 4, 5, 7, 3, 6, 8]

The way this method should work is this:
1. Starting from the right, find the first number that is smaller than the number to its immediate right.
[0, 1, 2, 9, 4, 5, 6, 8, 7, 3]
So here you have a tail of three increasing numbers (when going right to left), and 6 is the first that decreases.

2. The partial permutation formed by this number and the decreasing tail has to be rearranged to the next permutation in the numerical order. First increase that leading number by swapping it with the next higher one in that tail.
[0, 1, 2, 9, 4, 5, 7, 8, 6, 3]
Note that this still leaves the tail as a decreasing sequence.

3. The tail has to be rearranged to be the first in numerical order. This means it should become an increasing tail, i.e. the order has to be reversed.
[0, 1, 2, 9, 4, 5, 7, 3, 6, 8 ]

And now you're done. The first permutation after
[0, 1, 2, 9, 4, 5, 6, 8, 7, 3]
is
[0, 1, 2, 9, 4, 5, 7, 3, 6, 8]

User avatar
sparkyb
Posts: 1091
Joined: Thu Sep 06, 2007 7:30 pm UTC
Location: Camberville proper!
Contact:

Re: How to approach difficult problems?

Postby sparkyb » Mon Oct 13, 2008 2:06 pm UTC

jaap wrote:
luke77 wrote:Therefore, (I think) for the list from 0 to 9, there are 10! possible permutations.


Correct.

luke77 wrote:Assuming I do have a list, though, you have to go through 10!/10 or 9! digits to get to the first permutation where 0 is not the first digit.


If you were given the index number on this list of one of the permutations, you should therefore be able to work out what the first digit of the permutation should be. This leaves you with a smaller problem to solve, namely working out what the next 9 digits of the permutation are. That smaller problem can be solved in almost exactly the same way, hence recursion.


I'd like to bump this, because this was getting very close to the better way of solving this problem than listing out all the successive permutations. You were right in your assumption that there are 9! combinations with 0 as the first digit (because there are always 9! combinations of any remaining 9 digits). 9! = 362880. So that means the first 362880 start with 0 the next 362880 start with 1, ... the last 362880 permutations of the total 10! start with 9 (if you don't understand lexicographic ordering maybe we need to talk about that some more). Which block of 362880 permutations is the millionth in? Hint: if there are 362880*n permutations in the 1st through nth block (1 indexed), then the millionth would be in the n+1'th block where 362880*n<1000000<=362880*(n+1). Now you know the first digit. Remove that digit from the list. How many permutations into this block is the millionth permutation? Hint: 1000000-362880*n or rather the remainder, 1000000%362880. So we can repeat this problem (recurse) for the list of 9 remaining digits. How many permutations are in the block with the second digit being the lowest value in the list? and on....

Also, if you want list all the permutations as an exercise, and to learn lexicographic ordering, there is a recursive algorithm for that that might be easier to understand that Chibu's iterative one. His method of finding the next permutation from the previous is neat, but it is a little harder to see why it works, I think. Lexicographic ordering (for single digits) basically means if you strung them all together and made them big 10 digit numbers, it would be the strictly increasing order. The goal is every lower number before any number higher than it. So start with the most significant digit. Pick this to as low as possible. Now generate every permutation that begins with this number (notice I don't say how, doesn't this sound like a recursive step?). After that, pick the next smallest number to be the most significant. Generate every permutation that begins with that number. Etc.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How to approach difficult problems?

Postby Xanthir » Mon Oct 13, 2008 11:58 pm UTC

I'd skipped this problem temporarily, but luckily this thread reminded me of a concept I'd run into before - the factoradic numbering system - which let me solve this in no time at all. I'm on a school computer right now, which means I had to seek out an online lisp interpreter and rewrite a couple of basic Lisp functions that weren't available, but once I put down a few basic library functions, the whole thing was stupid simple.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Kirby54925
Posts: 36
Joined: Thu Dec 13, 2007 3:43 pm UTC

Re: How to approach difficult problems?

Postby Kirby54925 » Thu Oct 16, 2008 6:44 pm UTC

Xanthir wrote:I'd skipped this problem temporarily, but luckily this thread reminded me of a concept I'd run into before - the factoradic numbering system - which let me solve this in no time at all. I'm on a school computer right now, which means I had to seek out an online lisp interpreter and rewrite a couple of basic Lisp functions that weren't available, but once I put down a few basic library functions, the whole thing was stupid simple.

Thanks Xanthir for making me feel like an idiot :P I've been racking my brain about that problem for a few weeks, but ever since you introduced the idea of the factoradic number system, the lightbulb went up in my head...

Now I just have to code this solution up in Haskell and I shall be done. Shouldn't be too difficult.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: How to approach difficult problems?

Postby Xanthir » Fri Oct 17, 2008 7:04 pm UTC

No problem. Now that it's obvious how to do this, and you're doing it in Haskell which likely won't be very close to my Lisp solution, here's my solution:
Spoiler:

Code: Select all

(defun punch (n list)
    "Punches a 'hole' in a list, returning the list without the nth item."
  (append (subseq list 0 n) (subseq list (1+ n))))

(defun factorial (n) (if (< n 2) 1 (* n (factorial (- n 1)))))

(defun base10->factoradic (n)
  "Converts a base-10 number into a list comprising a big-endian factoradic number."
  (let ((maxfact
         (loop for maxfact upfrom 1
               when (> (factorial maxfact) n) return (1- maxfact))))
    (loop for num = n then (mod num (factorial fact))
          for fact downfrom maxfact
          collect (floor num (factorial fact))
          until (= 0 fact))))

(defun euler-24 (permutation targetlist &key
                 (permutelist (base10->factoradic permutation)))
  "Solves Euler problem 24.  Permutelist is the factoradic representation of the permutation you're looking for. Targetlist is the list you're permuting (must be already sorted)."
  (if (null targetlist)
      nil
      (cons (nth (car permutelist) targetlist)
            (euler-24 permutation
                      (punch (car permutelist) targetlist)
                      :permutelist
                      (cdr permutelist)))))

Solved by (euler-24 (base10->factoradic 999999) (list 0 1 2 3 4 5 6 7 8 9)).
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 8 guests