1
$\begingroup$

I'm trying to resolve an algorithm, basically is something like this: You have different components with a name and a value. For example:

Component-1 : 28
Component-2 : 351
Component-3 : 3457
Component-4 : 70552
Component-5 : 445903
Component-6 : 6346782 
Component-7 : 53129236
Component-8 : 632423456
Component-9 : 5477934933

And you have this value: 632869387. And, I want to know if the component-1 is inside of this value. For this case, you have to sum component-1 + component-5 + component-8.

Assuming that the component has one more digit than the component that precedes it. Is possible determine if an specific value is inside of the total, if you have both resources?

$\endgroup$
  • $\begingroup$ well, you could always do a brute force method, which should be O(n^3) to find out. But this question seems about an algorithm and not about Mathematica itself. $\endgroup$ – Nasser Mar 23 '19 at 3:48
  • $\begingroup$ @Nasser iterating values and trying to match the result, right? (Taking as base, the objective component) $\endgroup$ – MrMins Mar 23 '19 at 3:50
  • $\begingroup$ @Nasser I already have as small number of components. No more than 25, for a computer system, the permutation is not difficult. Good approach! $\endgroup$ – MrMins Mar 23 '19 at 4:00
  • 1
    $\begingroup$ Is this something you need to implement in the software Mathematica? $\endgroup$ – J. M. is in limbo Mar 23 '19 at 4:22
  • 1
    $\begingroup$ This is a variant of the Subset Sum Problem: en.wikipedia.org/wiki/Subset_sum_problem There are many algorithms published on SE and other sites. See for example mathematica.stackexchange.com/q/192308/26598 $\endgroup$ – Roman Mar 23 '19 at 16:46
1
$\begingroup$

Suppose you have a list of numbers c and you want to find how to add a subset of them whose total is a given number. The function

f[n_, c_List] := Select[Subsets[Range@Length@c],
            n == Total@Extract[c, List /@ #] &];

will return a list of lists of indices into the list c of those numbers which sum to n. As a simple example the code

f[10, {1, 2, 3, 5, 8, 13}]

returns

{{2, 5}, {2, 3, 4}}

because $\, 10 = 2 + 8 = 2 + 3 + 5.\,$

Given your test example we can use the code

c = {28, 351, 3457, 70552, 445903, 6346782, 53129236, 632423456};
f[632869387, c] 

which returns {{1, 5, 8}} as was expected.

$\endgroup$
1
$\begingroup$

You could use LinearProgramming:

findSubset[x_] := Replace[
    Quiet[
        Check[
            LinearProgramming[
                {1,1,1,1,1,1,1,1,1},
                {
                {28,351,3457,70552,445903,6346782,53129236,632423456, -x}
                },
                {{0,0}},
                {{0,1},{0,1},{0,1},{0,1},{0,1},{0,1},{0,1},{0,1},{1,1}},
                Integers
            ],
            $Failed,
            LinearProgramming::lpsnf
        ],
        {LinearProgramming::lpip,LinearProgramming::lpsnf}
    ],
    a_List :> Most[a]
]

Your example:

findSubset[632869387]

{1, 0, 0, 0, 1, 0, 0, 1}

Another example:

findSubset[632869388]

$Failed

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.