Problem 382 of Euler project
ankur rathi
Ranch Hand
Posts: 3830
posted 4 years ago
Hi,
I am trying to solve Problem 382 of Euler project  http://projecteuler.net/problem=382
One of the steps to solve this problem (with my logic) is, if you get an array of some numbers, you've to generate unique combinations from those numbers, minimum 3 numbers in a set. For example, if an array given is: 1 2 3 4 6.
The combinations will be:
1 2 3 4 6
2 3 4 6
3 4 6
2 4 6
2 3 6
2 3 4
1 3 4 6
1 4 6
1 3 6
1 3 4
1 2 4 6
1 2 6
1 2 4
1 2 3 6
1 2 3
1 2 3 4
I could write algorithm for it but it's not efficient. It takes hours to generate combinations from an array of 25 numbers. Here is my code:
I am sure there could be many improvements in it or this algorithm whole could be discarded...
Please suggest...
Thanks.
I am trying to solve Problem 382 of Euler project  http://projecteuler.net/problem=382
One of the steps to solve this problem (with my logic) is, if you get an array of some numbers, you've to generate unique combinations from those numbers, minimum 3 numbers in a set. For example, if an array given is: 1 2 3 4 6.
The combinations will be:
1 2 3 4 6
2 3 4 6
3 4 6
2 4 6
2 3 6
2 3 4
1 3 4 6
1 4 6
1 3 6
1 3 4
1 2 4 6
1 2 6
1 2 4
1 2 3 6
1 2 3
1 2 3 4
I could write algorithm for it but it's not efficient. It takes hours to generate combinations from an array of 25 numbers. Here is my code:
I am sure there could be many improvements in it or this algorithm whole could be discarded...
Please suggest...
Thanks.
ankur rathi
Ranch Hand
Posts: 3830
posted 4 years ago
Also placing problem here for those who don't want to register...
A polygon is a flat shape consisting of straight line segments that are joined to form a closed chain or circuit. A polygon consists of at least three sides and does not selfintersect.
A set S of positive numbers is said to generate a polygon P if:
no two sides of P are the same length,
the length of every side of P is in S, and
S contains no other value.
For example:
The set {3, 4, 5} generates a polygon with sides 3, 4, and 5 (a triangle).
The set {6, 9, 11, 24} generates a polygon with sides 6, 9, 11, and 24 (a quadrilateral).
The sets {1, 2, 3} and {2, 3, 4, 9} do not generate any polygon at all.
Consider the sequence s, defined as follows:
s1 = 1, s2 = 2, s3 = 3
sn = sn1 + sn3 for n > 3.
Let Un be the set {s1, s2, ..., sn}. For example, U10 = {1, 2, 3, 4, 6, 9, 13, 19, 28, 41}.
Let f(n) be the number of subsets of Un which generate at least one polygon.
For example, f(5) = 7, f(10) = 501 and f(25) = 18635853.
Find the last 9 digits of f(1018).
Liar, liar, pants on fire! refreshing plug:
the new thread boost feature brings a LOT of attention to your favorite threads
https://coderanch.com/t/674455/ThreadBoostfeature
