x404.co.uk
http://www.x404.co.uk/forum/

Combinatorics
http://www.x404.co.uk/forum/viewtopic.php?f=4&t=14539		 Page 1 of 1
Author:  Fogmeister [ Tue Aug 23, 2011 12:18 pm ]
Post subject:  Combinatorics
I keep seeing this mentioned all over Project Euler and wondered what it is?

Is it purely just calculating the nCr solution to a problem and then working out the answer to that solution?

Or is there something more involed?

For instance, I search on wiki and it starts mentioning binary trees and stuff. Anyone got any good links of where to look at this from the point of view of programming?
Author:  jonlumb [ Tue Aug 23, 2011 12:31 pm ]
Post subject:  Re: Combinatorics
Combinatorics is (from what I remember) the process of counting without counting.

nCr work in some circumstances (such as is seen on Euler) but it covers other bits as well. Factorials crop up a lot.
Author:  Fogmeister [ Tue Aug 23, 2011 12:42 pm ]
Post subject:  Re: Combinatorics
OK, so if the question was ...

There are 10 counters numbered from 0 to 9. How many ways of picking 3 counters are there?

That would be an nCr using n = 10 and r = 3.

10C3 = 10! / 3!(10-3)!
= 10! / 3! x 7!
= 8 x 9 x 10 / 6
= 120

I can understand that and it's a fairly easy equation to come up with from basic principles.

According to the Project Euler forums there is a combinatorics solution to Problem 37...
[quote="Problem 37"]The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.[/quiote]
How would you work this back to combinatorics?

Even question 15 (routes through a 20x20 grid) is screaming out to me to be a combinatorics solution but I can't for the life of me work out how you would find the solution to it?

I think I need to go back and start learning this stuff again :D
Author:  jonlumb [ Tue Aug 23, 2011 12:46 pm ]
Post subject:  Re: Combinatorics
Realising there was a combinatorics route to solve 15 was how I did it. I haven't worked out a procedural method for getting the answer.

Hint:
It helps to realise that every route is the same length, and is always an equal split of right and down moves...
Author:  Fogmeister [ Tue Aug 23, 2011 12:56 pm ]
Post subject:  Re: Combinatorics
jonlumb wrote:
Realising there was a combinatorics route to solve 15 was how I did it. I haven't worked out a procedural method for getting the answer.

Hint:
It helps to realise that every route is the same length, and is always an equal split of right and down moves...

Ah ok.
I kind of did it in a very basic shortest path algorithm but instead o counting the path length I counted the number of times I went to each point.

i.e. the number of routes to each point is just the sum of the number of routes to the point immediately above it and to the left of it.

...I just got your hint!

OK, starting to work it out.
Author:  Fogmeister [ Tue Aug 23, 2011 1:04 pm ]
Post subject:  Re: Combinatorics
OK, so I've worked out the grid one.

Each route in a 20x20 grid is made up of 40 steps. 20 of them are sideways and 20 are down.

The solution is then just a basic nCr of how many ways there are to choose 20 down stesp out of 40 total steps.

i.e. 40C20 = 137846528820
Author:  Fogmeister [ Tue Aug 23, 2011 1:18 pm ]
Post subject:  Re: Combinatorics
OK, so I get that but then why would you need a computer program to solve it?

Sorry if I seem like I'm being an idiot.

There is a question about lexicographic permutations of 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9.

I can kind of see how the combinatoric solution would go but then it removes the need for a computer program surely?
Author:  rustybucket [ Tue Aug 23, 2011 1:20 pm ]
Post subject:  Re: Combinatorics
Combinatrix

That so should be something else... :lol:
Author:  jonbwfc [ Tue Aug 23, 2011 4:30 pm ]
Post subject:  Re: Combinatorics
rustybucket wrote:
Combinatrix
That so should be something else... :lol:

What, like a character in Asterix the Gaul?
Author:  rustybucket [ Tue Aug 23, 2011 4:38 pm ]
Post subject:  Re: Combinatorics
jonbwfc wrote:
rustybucket wrote:
Combinatrix
That so should be something else... :lol:

What, like a character in Asterix the Gaul?

Dom.....
Author:  JJW009 [ Tue Aug 23, 2011 4:57 pm ]
Post subject:  Re: Combinatorics
A leather clad hairdresser?
Author:  Fogmeister [ Wed Aug 24, 2011 11:50 am ]
Post subject:  Re: Combinatorics
Ah!

I figured out 24 using a combinatoric algorithm... although I did it in Excel.

Going to try to write a program to do the same thing.
Page 1 of 1 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/