Combination Testing to a predefined value

[kivan.maharaj]

What I want to do is write a program to test lexicographical
combinations of various sets of numbers to a predefined number and
write that true values to a text file.

Example:

Number choosen between 1 and 50

Number set = 6

Value test = 150

Save to = 150.txt

So what happens is you are using 50 numbers in sets of 6 to test the
sets to equal to 150 and

save to file 150.txt

01 02 03 04 05 06 = 21 False -> Discard
01 10 20 30 40 49 = 150 True -> Store number set in text file


Any ideas would be appreciated as I am fairly new to C++ and would like
to make the program flexible to test any numbers and number sets.

Thanks

 

[mlimber]

What I want to do is write a program to test lexicographical
combinations of various sets of numbers to a predefined number and
write that true values to a text file.

Example:

Number choosen between 1 and 50

Number set = 6

Value test = 150

Save to = 150.txt

So what happens is you are using 50 numbers in sets of 6 to test the
sets to equal to 150 and

save to file 150.txt

01 02 03 04 05 06 = 21 False -> Discard
01 10 20 30 40 49 = 150 True -> Store number set in text file


Any ideas would be appreciated as I am fairly new to C++ and would like
to make the program flexible to test any numbers and number sets.

Thanks

It is not at all clear to me what you are trying to do. What is the
"number set"? What is the "value test"? Are both of those supplied by
the user? Are the "number sets" supplied by the user? Do you always
just add the numbers together to see if the sum is equal to the "value
test"? Etc.

Please clarify, and perhaps we can help more.

Cheers! --M

 

[kivan.maharaj]

The number sets , value test and number range will always be supplied
by the user.

If the user wants to test a number set of 5 numbers between 1 and 50
that will give the total of 100 ,then they will provide that.

So it will be
Range: 1 to 50
Number Set: 5
Value: 100
20 30 35 5 10 = 100 .

For now it will be only be adding the numbers. The other thing is that
each test will be a unigue set so that there is no confusion with
repeat sets of numbers


Only the number set will be stored in the text file.

Hope this helps

 

[Richard Herring]

The number sets , value test and number range will always be supplied
by the user.

If the user wants to test a number set of 5 numbers between 1 and 50
that will give the total of 100 ,then they will provide that.

So it will be
Range: 1 to 50
Number Set: 5
Value: 100
20 30 35 5 10 = 100 .

For now it will be only be adding the numbers. The other thing is that
each test will be a unigue set so that there is no confusion with
repeat sets of numbers

So you're looking for an algorithm to find unique *partitions* of the
total into sets of numbers each within the given range?

This sounds like a general algorithms problem, rather than anything
specific to C++. How about asking somewhere like comp.programming?

 

[Howard Hinnant]

What I want to do is write a program to test lexicographical
combinations of various sets of numbers to a predefined number and
write that true values to a text file.

Example:

Number choosen between 1 and 50

Number set = 6

Value test = 150

Save to = 150.txt

So what happens is you are using 50 numbers in sets of 6 to test the
sets to equal to 150 and

save to file 150.txt

01 02 03 04 05 06 = 21 False -> Discard
01 10 20 30 40 49 = 150 True -> Store number set in text file


Any ideas would be appreciated as I am fairly new to C++ and would like
to make the program flexible to test any numbers and number sets.

Personally I would start by writing a generic algorithm with the
following signature and semantics:

template<class Function, class BidirectionalIterator, class Size>
Function
for_each_combination(BidirectionalIterator first,
BidirectionalIterator last,
Size k, Function f);

Requires: [first, last) is a valid range.

Effects: For each combination of elements in [first, last) taken k at a
time, permutes those elements into the range [first, first+k) and calls
f(first, first+k). If k < 1, no calls to f are made. If k >
last-first, it is truncated to last-first.

Notes: The effects clause does not imply random access. Iterator
addition used only for concise statements.

Returns f.

This is a valuable general purpose tool.

Then I would write a test functor more geared to your problem which has
an operator taking a range of int's, sums them up (perhaps using
std::accumulate), compares the sum to the proper number (perhaps given
during the functor's constructor), and if equal, process the desired
range in the desired way.

Finally a driver program could create the array, and call
for_each_combination with the appropriately created test functor.

The implementation of for_each_combination is definitely the hard part
in this exercise. But fwiw, there are 183723 combinations of numbers in
the range [1, 50], where six of them add up to 150 (out of a total of
nearly 16 million combinations).

There are cheaper algorithms for this particular computation. But
having the for_each_combination function in your tool box is worth the
time creating it. It is much more general, and if nothing else, would
help you test a more specialized but higher performing algorithm for
this problem.

-Howard