Win a copy of Testing JavaScript Applications this week in the HTML Pages with CSS and JavaScript forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Ron McLeod
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Tim Cooke
• Liutauras Vilda
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• fred rosenberger
• salvin francis
Bartenders:
• Piet Souris
• Frits Walraven
• Carey Brown

# Problem 382 of Euler project

Ranch Hand
Posts: 3851
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...

Thanks.

ankur rathi
Ranch Hand
Posts: 3851
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 self-intersect.

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 = sn-1 + sn-3 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).