Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8247 > unrolled thread

Looking for simple brute force solution

Back to article view | Back to comp.programming

Contents

  Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-03 23:18 +0000
    Re: Looking for simple brute force solution fir <profesor.fir@gmail.com> - 2018-01-03 16:49 -0800
      Re: Looking for simple brute force solution fir <profesor.fir@gmail.com> - 2018-01-03 17:11 -0800
        Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 10:14 +0000
          Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 10:52 -0500
            Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 16:46 +0000
              Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 12:37 -0500
    Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-03 21:28 -0500
      Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 09:42 +0000
        Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 10:16 -0500
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 17:26 +0000
            Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:19 +0000
    Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 02:29 +0000
      Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 09:55 +0000
        Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 14:29 +0000
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 16:55 +0000
            Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 20:36 +0000
        Re: Looking for simple brute force solution Robert Wessel <robertwessel2@yahoo.com> - 2018-01-04 12:03 -0600
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:28 +0000
            Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:50 +0000
              Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 23:06 +0000
              Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 21:35 -0500
                Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-05 05:59 +0000
                  Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-05 16:48 +0000
                  Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-06 08:50 -0500
                    Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-06 16:47 +0000

Page 1 of 2  [1] 2  Next page →

#8247 — Looking for simple brute force solution

Suppose you have a problem each of N items is to be included
or excluded and any combination of these items yields some
figure of merit. A brute force solution to determine the
best combination is to realize there are 2^N possible
combinations and you can run a counter from 0 to 2^N and
examine the bits of each counter to determine whether the
corresponding item is included (1) or excluded (0).

I have a similar problem with a list of numbers, say
20 numbers. Each number can either be ignored, added
to a running sum, or subtracted from the running sum.
The problem is to find the combination such that the
running sum is closest to a given value.

Since there are 3 options for each number there are
3^N possible cases for a list of N numbers. I tried
thinking about expanding the number of options to
4 so that two bits of a counter running from 0 to
4^N could be used but this runs up the number of
tests very rapidly. 3^10  is about 59,000 tries,
4^10 is over a million.

I am willing to suffer through a brute force method
because I don't have to solve a large number of these
problems, but I would like a solution that I could
use for a list of 20 or 30 numbers.

Background:
This problem arises from trying to read entries in
financial statements in which some entries are totals
of other entries but the meaning of the entries is
not well defined. It is as in an income statement
in which some entries are sources of income, some
are expenses, and some are intermediate sums of
other entries.

I hope I have described the problem sufficiently well
to spark a solution in your mind. If so, I thank
you for sharing that spark.

[toc] | [next] | [standalone]

#8248

W dniu czwartek, 4 stycznia 2018 00:18:10 UTC+1 użytkownik root napisał:
> Suppose you have a problem each of N items is to be included
> or excluded and any combination of these items yields some
> figure of merit. A brute force solution to determine the
> best combination is to realize there are 2^N possible
> combinations and you can run a counter from 0 to 2^N and
> examine the bits of each counter to determine whether the
> corresponding item is included (1) or excluded (0).
> 
> I have a similar problem with a list of numbers, say
> 20 numbers. Each number can either be ignored, added
> to a running sum, or subtracted from the running sum.
> The problem is to find the combination such that the
> running sum is closest to a given value.
> 
> Since there are 3 options for each number there are
> 3^N possible cases for a list of N numbers. I tried
> thinking about expanding the number of options to
> 4 so that two bits of a counter running from 0 to
> 4^N could be used but this runs up the number of
> tests very rapidly. 3^10  is about 59,000 tries,
> 4^10 is over a million.
> 
> I am willing to suffer through a brute force method
> because I don't have to solve a large number of these
> problems, but I would like a solution that I could
> use for a list of 20 or 30 numbers.
> 
> Background:
> This problem arises from trying to read entries in
> financial statements in which some entries are totals
> of other entries but the meaning of the entries is
> not well defined. It is as in an income statement
> in which some entries are sources of income, some
> are expenses, and some are intermediate sums of
> other entries.
> 
> I hope I have described the problem sufficiently well
> to spark a solution in your mind. If so, I thank
> you for sharing that spark.

in fact i think it is badny described, 
put it presisely give some example etc

[toc] | [prev] | [next] | [standalone]

#8249

W dniu czwartek, 4 stycznia 2018 01:49:21 UTC+1 użytkownik fir napisał:
> W dniu czwartek, 4 stycznia 2018 00:18:10 UTC+1 użytkownik root napisał:
> > Suppose you have a problem each of N items is to be included
> > or excluded and any combination of these items yields some
> > figure of merit. A brute force solution to determine the
> > best combination is to realize there are 2^N possible
> > combinations and you can run a counter from 0 to 2^N and
> > examine the bits of each counter to determine whether the
> > corresponding item is included (1) or excluded (0).
> > 
> > I have a similar problem with a list of numbers, say
> > 20 numbers. Each number can either be ignored, added
> > to a running sum, or subtracted from the running sum.
> > The problem is to find the combination such that the
> > running sum is closest to a given value.
> > 
> > Since there are 3 options for each number there are
> > 3^N possible cases for a list of N numbers. I tried
> > thinking about expanding the number of options to
> > 4 so that two bits of a counter running from 0 to
> > 4^N could be used but this runs up the number of
> > tests very rapidly. 3^10  is about 59,000 tries,
> > 4^10 is over a million.
> > 
> > I am willing to suffer through a brute force method
> > because I don't have to solve a large number of these
> > problems, but I would like a solution that I could
> > use for a list of 20 or 30 numbers.
> > 
> > Background:
> > This problem arises from trying to read entries in
> > financial statements in which some entries are totals
> > of other entries but the meaning of the entries is
> > not well defined. It is as in an income statement
> > in which some entries are sources of income, some
> > are expenses, and some are intermediate sums of
> > other entries.
> > 
> > I hope I have described the problem sufficiently well
> > to spark a solution in your mind. If so, I thank
> > you for sharing that spark.
> 
> in fact i think it is badny described, 
> put it presisely give some example etc

specifically i dont ger what is running sum (maybe becouse my weak english)

soeme ide i got as fat as i managed to understood this problem (i understood the problem isyou gave say 50 doubles with some random values 
and you gor soem double named it S and you wnat chose some subes form this set of 50 which by combinations of additions of subtractions will be closest to S)

I dont know, though it seem like pureli mathematical task, probably well solved by mathematicians

some idea i only got would be sort those numbers by value, then by chosing the combinations you will not need to tray all but only those that will be close to expected summ - that would 
spare checking a lot of combinations

also there maybe is possible to make tables of sum of differences, make soem higher ranks of it
too, sort it by value - this sortig then can spare checking all values becouse there will only need to be checked those closed to expected values, i think sorting may spare blind checking all with another all
 besides that prbablu matematicians resolved that

[toc] | [prev] | [next] | [standalone]

#8254

fir <profesor.fir@gmail.com> wrote:
>> 
>> in fact i think it is badny described, 
>> put it presisely give some example etc
>
> specifically i dont ger what is running sum (maybe becouse my weak english)

A running sum of a sequence of numbers is the sum of all preceding
numbers. For the sequence of numbers 1,2,3,4,... the running
sums would be 1, 3, 6, 10,....

In a Statement Of Income, it is common for some items to be
stated individually and then be followed by a sum of those
items:

cost of materials 100.
cost of assembly   45.
cost of item      145.
cost of shipping   11.
total cost        156.


In this list it is easy to see that we can take the
first, second, and fourth items to account for the total
cost. We have to ignore the intermediate term 145.

>
> soeme ide i got as fat as i managed to understood this problem (i understood the problem isyou gave say 50 doubles with some random values 
> and you gor soem double named it S and you wnat chose some subes form this set of 50 which by combinations of additions of subtractions will be closest to S)

I'm sorry, I don't understand what you are saying here.

>
> I dont know, though it seem like pureli mathematical task, probably well solved by mathematicians

I agree that the problem falls into the category of integer programming. However
I don't have an integer programming package and for the number of times I
need to solve this problem I thought a simple brute force method would
be more efficient of my time.

>
> some idea i only got would be sort those numbers by value, then by chosing the combinations you will not need to tray all but only those that will be close to expected summ - that would 
> spare checking a lot of combinations

There might be some efficiency in that approach. In my example above sorting the numbers
into 11, 45, 100, 145 we could eliminate any sums that included both 100 and 145.
>
> also there maybe is possible to make tables of sum of differences, make soem higher ranks of it
> too, sort it by value - this sortig then can spare checking all values becouse there will only need to be checked those closed to expected values, i think sorting may spare blind checking all with another all
>  besides that prbablu matematicians resolved that

[toc] | [prev] | [next] | [standalone]

#8257

On 1/4/18 5:14 AM, root wrote:
> cost of materials 100.
> cost of assembly   45.
> cost of item      145.
> cost of shipping   11.
> total cost        156.
> 
> 
> In this list it is easy to see that we can take the
> first, second, and fourth items to account for the total
> cost. We have to ignore the intermediate term 145.

It sounds like your goal is to transform that list into something like;


         100   Cost of materials
          45   Cost of Assembly
     145      Cost of Item
      11      Cost of Shipping
156         Total Cost

Where you assign everything a 'level' (the grand sum being level 0) and 
a given level is the sum of all the items 1 level higher between it and 
the previous item of its level. It sounds like you also want to allow 
some items to be negated for the sum, as credits/debits aren't carefully 
indicated (which actually make the process much tougher). If at all 
possible, I would try to understand the category names and assign a sign 
to them, even if I had to try a couple possibilities, as only having 
sums and no differences makes things much simpler.

Now if 'running sums' aren't actually right after the items they are the 
sum for, then you probably need to brute force the solution.

IF you can try assigning signs to values to make it so you are always 
adding, then you can work starting at the top of the list with the 
second item (as the first can't be a running sum) and see if that item 
is the sum of some number of items before it that aren't part of a 
previously detected running sum, and if you find such a case, mark it as 
a running sum, and push everything that went into it up a level (and 
things that made them up a level too).

Note, this means that Cost of Shipping would only check if it was 'sum 
of Cost of Item, and not include Cost of Assembly, as this is already 
accounted for.

There is a chance that you may miss-detect some running sums if the 
numbers aren't accurate or just happen to add up, and for a one-off, 
just outputting that detection may be enough (or even do it by hand, as 
the human brain is better at detecting suspicious conditions) for you to 
manually adjust things.

If you really need to do it programmatically, you can add back tracking 
where you systematically undo marking things as possible running sums 
until you get to a suitable result.

[toc] | [prev] | [next] | [standalone]

#8258

Richard Damon <Richard@Damon-Family.org> wrote:
> On 1/4/18 5:14 AM, root wrote:
>> cost of materials 100.
>> cost of assembly   45.
>> cost of item      145.
>> cost of shipping   11.
>> total cost        156.
>> 
>> 
>> In this list it is easy to see that we can take the
>> first, second, and fourth items to account for the total
>> cost. We have to ignore the intermediate term 145.
>
> It sounds like your goal is to transform that list into something like;
>
>
>          100   Cost of materials
>           45   Cost of Assembly
>      145      Cost of Item
>       11      Cost of Shipping
> 156         Total Cost
>
> Where you assign everything a 'level' (the grand sum being level 0) and 
> a given level is the sum of all the items 1 level higher between it and 
> the previous item of its level. It sounds like you also want to allow 
> some items to be negated for the sum, as credits/debits aren't carefully 
> indicated (which actually make the process much tougher). If at all 
> possible, I would try to understand the category names and assign a sign 
> to them, even if I had to try a couple possibilities, as only having 
> sums and no differences makes things much simpler.

It would make sense that in the income statement expenses would always
have a minus sign, but in my data that isn't true. In order for the
numbers to work out, some of the expenses have to be added to
income. For example, the entry "Total Interest Expense" has to
be subtracted from income. Several lines down, "Other Interest Expense"
has to be added to income for the numbers to hang together. It would
make sense that Other Interest Expense should be ignored as having
already been included in Total Interest Expense.

I am resorting to the brute force method because too many of the
items I see don't make sense to me.
>
> Now if 'running sums' aren't actually right after the items they are the 
> sum for, then you probably need to brute force the solution.

In my case, the running sums are generally ahead of the individual
items, but are not identified as running sums. Not only that, but
some items which are identified as "expense" are added to income
instead of subtracted.

>
> IF you can try assigning signs to values to make it so you are always 
> adding, then you can work starting at the top of the list with the 
> second item (as the first can't be a running sum) and see if that item 
> is the sum of some number of items before it that aren't part of a 
> previously detected running sum, and if you find such a case, mark it as 
> a running sum, and push everything that went into it up a level (and 
> things that made them up a level too).
>
> Note, this means that Cost of Shipping would only check if it was 'sum 
> of Cost of Item, and not include Cost of Assembly, as this is already 
> accounted for.
>
> There is a chance that you may miss-detect some running sums if the 
> numbers aren't accurate or just happen to add up, and for a one-off, 

My numbers are only good for 4 digits. That means that when my best
understanding is off by a "little" I can't be sure that I haven't
made a mistake.

There are three types of reports in financial statements: income, balance,
and cash-flow. The numbers in all three reports have to be consistent,
and that is a higher level of difficulty. Whatever I deduce from the
income statement has to correspond to what I infer from the cash-flow
statement and that isn't working out given the accuracy of the numbers
I have.

> just outputting that detection may be enough (or even do it by hand, as 
> the human brain is better at detecting suspicious conditions) for you to 
> manually adjust things.
>
> If you really need to do it programmatically, you can add back tracking 
> where you systematically undo marking things as possible running sums 
> until you get to a suitable result.

That is what the brute force method is doing.
>

[toc] | [prev] | [next] | [standalone]

#8261

On 1/4/18 11:46 AM, root wrote:
> Richard Damon <Richard@Damon-Family.org> wrote:
>> On 1/4/18 5:14 AM, root wrote:
>>> cost of materials 100.
>>> cost of assembly   45.
>>> cost of item      145.
>>> cost of shipping   11.
>>> total cost        156.
>>>
>>>
>>> In this list it is easy to see that we can take the
>>> first, second, and fourth items to account for the total
>>> cost. We have to ignore the intermediate term 145.
>>
>> It sounds like your goal is to transform that list into something like;
>>
>>
>>           100   Cost of materials
>>            45   Cost of Assembly
>>       145      Cost of Item
>>        11      Cost of Shipping
>> 156         Total Cost
>>
>> Where you assign everything a 'level' (the grand sum being level 0) and
>> a given level is the sum of all the items 1 level higher between it and
>> the previous item of its level. It sounds like you also want to allow
>> some items to be negated for the sum, as credits/debits aren't carefully
>> indicated (which actually make the process much tougher). If at all
>> possible, I would try to understand the category names and assign a sign
>> to them, even if I had to try a couple possibilities, as only having
>> sums and no differences makes things much simpler.
> 
> It would make sense that in the income statement expenses would always
> have a minus sign, but in my data that isn't true. In order for the
> numbers to work out, some of the expenses have to be added to
> income. For example, the entry "Total Interest Expense" has to
> be subtracted from income. Several lines down, "Other Interest Expense"
> has to be added to income for the numbers to hang together. It would
> make sense that Other Interest Expense should be ignored as having
> already been included in Total Interest Expense.
> 
> I am resorting to the brute force method because too many of the
> items I see don't make sense to me.
>>
>> Now if 'running sums' aren't actually right after the items they are the
>> sum for, then you probably need to brute force the solution.
> 
> In my case, the running sums are generally ahead of the individual
> items, but are not identified as running sums. Not only that, but
> some items which are identified as "expense" are added to income
> instead of subtracted.

If they are consistently in front, then it should still be possible to 
try to identify the possible running sums (you just start at the bottom 
and work up).

I suppose if you are a bit sloppy with terms, and 'expense' could 
sometimes be something you bill your customers, and thus be an income 
category (likely with some other expense item somewhere else that 
decreases income as a justification for it, a bit like the added fees in 
a lot of services which indirectly reference government fees and taxes 
that they are sort of forwarding to their customers).

> 
>>
>> IF you can try assigning signs to values to make it so you are always
>> adding, then you can work starting at the top of the list with the
>> second item (as the first can't be a running sum) and see if that item
>> is the sum of some number of items before it that aren't part of a
>> previously detected running sum, and if you find such a case, mark it as
>> a running sum, and push everything that went into it up a level (and
>> things that made them up a level too).
>>
>> Note, this means that Cost of Shipping would only check if it was 'sum
>> of Cost of Item, and not include Cost of Assembly, as this is already
>> accounted for.
>>
>> There is a chance that you may miss-detect some running sums if the
>> numbers aren't accurate or just happen to add up, and for a one-off,
> 
> My numbers are only good for 4 digits. That means that when my best
> understanding is off by a "little" I can't be sure that I haven't
> made a mistake.

If by 4 digits, you mean something like order of a million, but only 
reported to thousands, so there is some round off, this adds a bit of 
complication to detecting possible running sums, but should be 
manageable. Basically the tolerance of a sum is based on how many terms 
that make it up. If you really mean 4 digits, so numbers in the 100 
thousands are reported to 100s, while numbers in the millions are 
reported to thousands, that sounds very strange. If they actually report 
numbers with 'significant digits' (non-zero) that might actually wrong, 
that is very strange to me, but again, could be handled by tolerancing 
the definition of matching to the various numbers in the sum.

> 
> There are three types of reports in financial statements: income, balance,
> and cash-flow. The numbers in all three reports have to be consistent,
> and that is a higher level of difficulty. Whatever I deduce from the
> income statement has to correspond to what I infer from the cash-flow
> statement and that isn't working out given the accuracy of the numbers
> I have.

If you really have 3 columns of numbers for the same category line 
items, that could provide a strong test to remove a lot of false running 
sums.
> 
>> just outputting that detection may be enough (or even do it by hand, as
>> the human brain is better at detecting suspicious conditions) for you to
>> manually adjust things.
>>
>> If you really need to do it programmatically, you can add back tracking
>> where you systematically undo marking things as possible running sums
>> until you get to a suitable result.
> 
> That is what the brute force method is doing.
>>

The difference is that if you do a bit of the work to decide which terms 
might be running sums (and thus mask off their component parts) you 
greatly break down the combitorial explosion.

[toc] | [prev] | [next] | [standalone]

#8250

On 1/3/18 6:18 PM, root wrote:
> Suppose you have a problem each of N items is to be included
> or excluded and any combination of these items yields some
> figure of merit. A brute force solution to determine the
> best combination is to realize there are 2^N possible
> combinations and you can run a counter from 0 to 2^N and
> examine the bits of each counter to determine whether the
> corresponding item is included (1) or excluded (0).
> 
> I have a similar problem with a list of numbers, say
> 20 numbers. Each number can either be ignored, added
> to a running sum, or subtracted from the running sum.
> The problem is to find the combination such that the
> running sum is closest to a given value.
> 
> Since there are 3 options for each number there are
> 3^N possible cases for a list of N numbers. I tried
> thinking about expanding the number of options to
> 4 so that two bits of a counter running from 0 to
> 4^N could be used but this runs up the number of
> tests very rapidly. 3^10  is about 59,000 tries,
> 4^10 is over a million.
> 
> I am willing to suffer through a brute force method
> because I don't have to solve a large number of these
> problems, but I would like a solution that I could
> use for a list of 20 or 30 numbers.
> 
> Background:
> This problem arises from trying to read entries in
> financial statements in which some entries are totals
> of other entries but the meaning of the entries is
> not well defined. It is as in an income statement
> in which some entries are sources of income, some
> are expenses, and some are intermediate sums of
> other entries.
> 
> I hope I have described the problem sufficiently well
> to spark a solution in your mind. If so, I thank
> you for sharing that spark.
> 

Brute force method:

One simple method would be to have an array, the same size as the number 
of numbers, with values representing the options, maybe 0 for ignore, 1 
to add, -1 to subtract.

1) Start all elements a 0.

2) process.

3) Take the first element, move it to the next value in the sequence,
0 -> 1 -> -1 -> 0

if it became 0, then move to the next element and repeat until you 
sequence and element and it doesn't become 0, or you run out of elements 
(then you are done).

go back to 2 and process


This is basically counting base 3.

[toc] | [prev] | [next] | [standalone]

#8252

Richard Damon <Richard@Damon-Family.org> wrote:
>
> Brute force method:
>
> One simple method would be to have an array, the same size as the number 
> of numbers, with values representing the options, maybe 0 for ignore, 1 
> to add, -1 to subtract.
>
> 1) Start all elements a 0.
>
> 2) process.
>
> 3) Take the first element, move it to the next value in the sequence,
> 0 -> 1 -> -1 -> 0
>
> if it became 0, then move to the next element and repeat until you 
> sequence and element and it doesn't become 0, or you run out of elements 
> (then you are done).
>
> go back to 2 and process
>
>
> This is basically counting base 3.
>

I can only see how to do this with a sequence of N nested loops.
Each loop is of the form:

for(j=-1;j<2;++j){
	....
	}

which is how I started. Programming this is rather cumbersome
so I was hoping to find another approach.

The problem becomes combinatorially explosive for N between
10 and 20.

[toc] | [prev] | [next] | [standalone]

#8256

On 1/4/18 4:42 AM, root wrote:
> Richard Damon <Richard@Damon-Family.org> wrote:
>>
>> Brute force method:
>>
>> One simple method would be to have an array, the same size as the number
>> of numbers, with values representing the options, maybe 0 for ignore, 1
>> to add, -1 to subtract.
>>
>> 1) Start all elements a 0.
>>
>> 2) process.
>>
>> 3) Take the first element, move it to the next value in the sequence,
>> 0 -> 1 -> -1 -> 0
>>
>> if it became 0, then move to the next element and repeat until you
>> sequence and element and it doesn't become 0, or you run out of elements
>> (then you are done).
>>
>> go back to 2 and process
>>
>>
>> This is basically counting base 3.
>>
> 
> I can only see how to do this with a sequence of N nested loops.
> Each loop is of the form:
> 
> for(j=-1;j<2;++j){
> 	....
> 	}
> 
> which is how I started. Programming this is rather cumbersome
> so I was hoping to find another approach.
> 
> The problem becomes combinatorially explosive for N between
> 10 and 20.
> 

(untested code)

#define N 20
int index[N];
int i;

for(i=0; i<N; i++)
   index[N] = 0;

while(1)) {
   /* Do Stuff */

   /* Now, increment the state */
   i = 0;
   while(1) {
     if(index[i] == 1) index[N] = -1;
     else index[N] = index[N] +1;
     if(index[N] != 0) break; /* Have new number */
     i = i+1;		/* need to propagate the carry */
     if(i >= N) break;   /* Number overflowed */
   }
   if(i >= N) break;     /* Overflow goes all the wa out */
}

[toc] | [prev] | [next] | [standalone]

#8260

Richard Damon <Richard@Damon-Family.org> wrote:
> On 1/4/18 4:42 AM, root wrote:
>> Richard Damon <Richard@Damon-Family.org> wrote:
>>>
>>> Brute force method:
>>>
>>> One simple method would be to have an array, the same size as the number
>>> of numbers, with values representing the options, maybe 0 for ignore, 1
>>> to add, -1 to subtract.
>>>
>>> 1) Start all elements a 0.
>>>
>>> 2) process.
>>>
>>> 3) Take the first element, move it to the next value in the sequence,
>>> 0 -> 1 -> -1 -> 0
>>>
>>> if it became 0, then move to the next element and repeat until you
>>> sequence and element and it doesn't become 0, or you run out of elements
>>> (then you are done).
>>>
>>> go back to 2 and process
>>>
>>>
>>> This is basically counting base 3.
>>>
>
> (untested code)
>
> #define N 20
> int index[N];
> int i;
>
> for(i=0; i<N; i++)
>    index[N] = 0;
>
> while(1)) {
>    /* Do Stuff */
>
>    /* Now, increment the state */
>    i = 0;
>    while(1) {
>      if(index[i] == 1) index[N] = -1;
>      else index[N] = index[N] +1;
>      if(index[N] != 0) break; /* Have new number */
>      i = i+1;		/* need to propagate the carry */
>      if(i >= N) break;   /* Number overflowed */
>    }
>    if(i >= N) break;     /* Overflow goes all the wa out */
> }
>




As written the program doesn't terminate. I think in the inner loop
you mean index[i] when you write index[N]? Making those
changes the program terminates after 243 iterations which
is 3^5.

Here is the final program:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <termio.h>
#include <sys/wait.h>
#include <signal.h>
#include <time.h>
#include <sys/time.h>
#include <string.h>
#include <ctype.h>

#define N 5
int main(argc,argv)
int argc;
char **argv;
{
 int index[N];
 int i;
int j;

 for(i=0; i<N; i++)
    index[i] = 0;

 while(1) {
    /* Do Stuff */

for(j=0;j<N;++j) printf("%d ",index[j]);
printf("\n");
    /* Now, increment the state */
    i = 0;
    while(1) {
      if(index[i] == 1) index[i] = -1;
      else index[i] = index[i] +1;
      if(index[i] != 0) break; /* Have new number */
      i = i+1;     /* need to propagate the carry */
      if(i == N) break;   /* Number overflowed */
    }
    if(i == N) break;     /* Overflow goes all the wa out */
 }

}

Thanks for the suggestion. I'll keep this program.

[toc] | [prev] | [next] | [standalone]

#8264

root <NoEMail@home.org> wrote:

>SNIP program

I modified the program to "do stuff", and ran a case for N=12.
The run was completed in 24ms. I then modified the program to
halt when an exact fit was found. With that modification the
program ran in 1ms. Then I stepped up to N=20 and the case
ran in 14ms after getting an exact fit after 180,024 tries.

Here is the input to the program and the results:
+068  Interest Income                              5.366e+10
-069 Interest and Fees on Loans                    3.951e+10
+073 Other Interest or Dividend Income             1.416e+10
+075  Total Interest Expense                       5.91e+09
+076 Interest Expense on Bank Deposits             1.4e+09
-077 Other Interest Expense                        4.51e+09
-078 Interest Expense on Debt                      4.51e+09
082  Net Interest Income                          4.775e+10
+084  Loan Loss Provision                          3.77e+09
086  Net Interest Income after Provision          4.398e+10
087 Net Interest Inc After Loan Loss Prov Growth  2.62
089 Non-Interest Income                           4.195e+10
+090 Securities Gain                               2.35e+09
091 Trading Account Income                        1.03e+09
092 Trust Income, Commissions & Fees              3.038e+10
093 Commission & Fee Income                       2.704e+10
094 Other Operating Income                        8.19e+09
095 Non-Interest Expense                          5.322e+10
096 Labor & Related Expense                       3.189e+10
097 Equipment Expense                             5.01e+09
098 Other Operating Expense                       1.463e+10
=099  Operating Income                             3.272e+10

These are lines from the original source. The first and
last lines are not included in the iteration. The first
character in each line shows + if the value is added,
- if the value is subtracted and neither if the value
is ignored. Each line in the original source includes
a 3 digit line number.

So, I start with 5.366E10 interest income. Add/subtract entries
and end with Operating Income of 3.272E10.

See a problem? I think the result for line 075 Total Interest Expense
should not add to Interest Income. Moreover, Trading Account Income,
although small, should nevertheless be added.

Almost certainly the problem comes from early stopping. I am
rerunning the case to print out all solutions that exactly
fit. I don't expect it to finish today.

[toc] | [prev] | [next] | [standalone]

#8251

root <NoEMail@home.org> writes:
<snip>
> I have a similar problem with a list of numbers, say
> 20 numbers. Each number can either be ignored, added
> to a running sum, or subtracted from the running sum.
> The problem is to find the combination such that the
> running sum is closest to a given value.
>
> Since there are 3 options for each number there are
> 3^N possible cases for a list of N numbers. I tried
> thinking about expanding the number of options to
> 4 so that two bits of a counter running from 0 to
> 4^N could be used but this runs up the number of
> tests very rapidly. 3^10  is about 59,000 tries,
> 4^10 is over a million.

You can just count up to 3^N.  Call the count i.  For each number in the
set you use i%3 to determine if you add, subtract or ignore.  For the
next number you set i = i/3 and repeat.  In effect you are pulling out
the base-3 digits of i.  (I'm using % to mean remainder and / for
integer division.)

> I am willing to suffer through a brute force method
> because I don't have to solve a large number of these
> problems, but I would like a solution that I could
> use for a list of 20 or 30 numbers.

That's a lot of sums to calculate.  If you can do a million a second,
N=30 would take over 6.6 years.  N=20 is more manageable but even then I
think you might have to take some shortcuts.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8253

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> root <NoEMail@home.org> writes:
><snip>
>
> You can just count up to 3^N.  Call the count i.  For each number in the
> set you use i%3 to determine if you add, subtract or ignore.  For the
> next number you set i = i/3 and repeat.  In effect you are pulling out
> the base-3 digits of i.  (I'm using % to mean remainder and / for
> integer division.)

Yes, that is the solution I was looking for. Thanks.

I can do that with two nested loops instead of N.

>
>
> That's a lot of sums to calculate.  If you can do a million a second,
> N=30 would take over 6.6 years.  N=20 is more manageable but even then I
> think you might have to take some shortcuts.
>

On my machine a real case of N=12 took no noticeable time so I think that
I could easily handle N=15.  N=20 would be about 6,000 times as long,
but I could let the machine crank away over night.

The actual data are not very encouraging: there are 30 entries leading
up to the determination of operating income, and another 22 to reach
net income. The entries in the income statement do not conform to
any accounting standard familiar to me.

[toc] | [prev] | [next] | [standalone]

#8255

root <NoEMail@home.org> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> root <NoEMail@home.org> writes:
>><snip>
>>
>> You can just count up to 3^N.  Call the count i.  For each number in the
>> set you use i%3 to determine if you add, subtract or ignore.  For the
>> next number you set i = i/3 and repeat.  In effect you are pulling out
>> the base-3 digits of i.  (I'm using % to mean remainder and / for
>> integer division.)
>
> Yes, that is the solution I was looking for. Thanks.
>
> I can do that with two nested loops instead of N.

OK, but I don't see why you need two nested loops.  That's bad news
because you are squaring an already exponential function.

>> That's a lot of sums to calculate.  If you can do a million a second,
>> N=30 would take over 6.6 years.  N=20 is more manageable but even then I
>> think you might have to take some shortcuts.
>
> On my machine a real case of N=12 took no noticeable time so I think that
> I could easily handle N=15.  N=20 would be about 6,000 times as long,
> but I could let the machine crank away over night.

2^20 is 6,561 times 2^12, but if you have two 'N' nested loops, that
would be 6,561 * 6,561 = 43,046,721 times longer.

> The actual data are not very encouraging: there are 30 entries leading
> up to the determination of operating income, and another 22 to reach
> net income. The entries in the income statement do not conform to
> any accounting standard familiar to me.

It's not looking good.  You may need to find some good-enough answers,
or hope that the data are such that whole swathes of the search can be
eliminated.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8259

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> root <NoEMail@home.org> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>> root <NoEMail@home.org> writes:
>>><snip>
>>>
>>> You can just count up to 3^N.  Call the count i.  For each number in the
>>> set you use i%3 to determine if you add, subtract or ignore.  For the
>>> next number you set i = i/3 and repeat.  In effect you are pulling out
>>> the base-3 digits of i.  (I'm using % to mean remainder and / for
>>> integer division.)
>>
>> Yes, that is the solution I was looking for. Thanks.
>>
>> I can do that with two nested loops instead of N.
>
> OK, but I don't see why you need two nested loops.  That's bad news
> because you are squaring an already exponential function.

The outer loop is to count from 0 to 3^N. The inner loop is to
work the outer loop counter down to 0 via a sequence of /3
operations. Within the inner loop I have to keep track of how
many times I have done the /3 operation because that determines
which number in the table I am currently using.

>
>
> 2^20 is 6,561 times 2^12, but if you have two 'N' nested loops, that
> would be 6,561 * 6,561 = 43,046,721 times longer.

No, the inner loop is only dealing with the loop index of the outer
loop. The depth of the inner loop is the number of base 3 digits
it takes to express the outer loop index.

>
>
> It's not looking good.  You may need to find some good-enough answers,
> or hope that the data are such that whole swathes of the search can be
> eliminated.
>

I agree it's not looking good.

I really appreciate your insight and I have to add your idea to my bag
of programming tricks. It can easily be expanded to allow any number
of options for items in the list.

Thanks again.

[toc] | [prev] | [next] | [standalone]

#8263

root <NoEMail@home.org> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> root <NoEMail@home.org> writes:
>>
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>>>> root <NoEMail@home.org> writes:
>>>><snip>
>>>>
>>>> You can just count up to 3^N.  Call the count i.  For each number in the
>>>> set you use i%3 to determine if you add, subtract or ignore.  For the
>>>> next number you set i = i/3 and repeat.  In effect you are pulling out
>>>> the base-3 digits of i.  (I'm using % to mean remainder and / for
>>>> integer division.)
>>>
>>> Yes, that is the solution I was looking for. Thanks.
>>>
>>> I can do that with two nested loops instead of N.
>>
>> OK, but I don't see why you need two nested loops.  That's bad news
>> because you are squaring an already exponential function.
>
> The outer loop is to count from 0 to 3^N. The inner loop is to
> work the outer loop counter down to 0 via a sequence of /3
> operations.

Ah, right, so just what I was proposing.  The wording suggested to me
that the two loops had the same bounds.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#8262

On Thu, 4 Jan 2018 09:55:26 +0000 (UTC), root <NoEMail@home.org>
wrote:

>Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> root <NoEMail@home.org> writes:
>><snip>
>>
>> You can just count up to 3^N.  Call the count i.  For each number in the
>> set you use i%3 to determine if you add, subtract or ignore.  For the
>> next number you set i = i/3 and repeat.  In effect you are pulling out
>> the base-3 digits of i.  (I'm using % to mean remainder and / for
>> integer division.)
>
>Yes, that is the solution I was looking for. Thanks.
>
>I can do that with two nested loops instead of N.
>
>>
>>
>> That's a lot of sums to calculate.  If you can do a million a second,
>> N=30 would take over 6.6 years.  N=20 is more manageable but even then I
>> think you might have to take some shortcuts.
>>
>
>On my machine a real case of N=12 took no noticeable time so I think that
>I could easily handle N=15.  N=20 would be about 6,000 times as long,
>but I could let the machine crank away over night.
>
>The actual data are not very encouraging: there are 30 entries leading
>up to the determination of operating income, and another 22 to reach
>net income. The entries in the income statement do not conform to
>any accounting standard familiar to me.


Consider a meet-in-the-middle attack.  Create two arrays, of 3**15
elements each.  Each entry contains one of the 3**15 possible sums of
one half of the 30 input terms, plus the sequence that got you there.
Repeat for the other half of the 30 entries.  Creating the two arrays
will be about 14 million units of work each.  Sort one of the arrays
by the resulting sum, which ought to be O(n*logn) for n=14M.

Now step through unsorted array and subtract the sum in that entry
from the desired value.  Then binary search the sorted array for that
value.  If you find it, output the match with information from both
arrays.  If you don't find it, move on to the next item in the
unsorted array and repeat.  Again, O(n*logn).

This does require storage proportional to 3**15, but you should be
able to store a single array entry as one 64-bit integer and 15 bytes
(or less if you can pack the operations better, or the partial sum
fits in something smaller), so certainly well under a GB (2 * 32 *
3**15).

Several optimizations are possible.  For example, it's not actually
necessary to store the unsorted array (just test against the sorted
array, which does have to be generated first) as you generate the
elements.  Nor do the sorted and unsorted arays need to be the same
size.  If storage limitations limit the size of the sorted array, you
can just step through more entries in the unsorted array (say make the
unsorted array 3**14 entries, but them step through the 3**16 entries
for what would be the unsorted array).

This should make possible a reasonable time search on over 36 elements
on a reasonably sized desktop machine.

[toc] | [prev] | [next] | [standalone]

#8265

Robert Wessel <robertwessel2@yahoo.com> wrote:
> On Thu, 4 Jan 2018 09:55:26 +0000 (UTC), root <NoEMail@home.org>
> wrote:
>
>>Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>
>
> Consider a meet-in-the-middle attack.  Create two arrays, of 3**15
> elements each.  Each entry contains one of the 3**15 possible sums of
> one half of the 30 input terms, plus the sequence that got you there.
> Repeat for the other half of the 30 entries.  Creating the two arrays
> will be about 14 million units of work each.  Sort one of the arrays
> by the resulting sum, which ought to be O(n*logn) for n=14M.
>
> Now step through unsorted array and subtract the sum in that entry
> from the desired value.  Then binary search the sorted array for that
> value.  If you find it, output the match with information from both
> arrays.  If you don't find it, move on to the next item in the
> unsorted array and repeat.  Again, O(n*logn).
>
> This does require storage proportional to 3**15, but you should be
> able to store a single array entry as one 64-bit integer and 15 bytes
> (or less if you can pack the operations better, or the partial sum
> fits in something smaller), so certainly well under a GB (2 * 32 *
> 3**15).

3^15 is only 14M entries. I have 64GB memory on this machine.

I see your approach which suggests an FFT like approach of
successively dividing by 2.

>
> Several optimizations are possible.  For example, it's not actually
> necessary to store the unsorted array (just test against the sorted
> array, which does have to be generated first) as you generate the
> elements.  Nor do the sorted and unsorted arays need to be the same
> size.  If storage limitations limit the size of the sorted array, you
> can just step through more entries in the unsorted array (say make the
> unsorted array 3**14 entries, but them step through the 3**16 entries
> for what would be the unsorted array).
>
> This should make possible a reasonable time search on over 36 elements
> on a reasonably sized desktop machine.

We'll see how the case currently running turns out. I only have to work
out the solution for four or five cases then use that solution to
unravel data for about 420 data sets.

Thanks for your help.

[toc] | [prev] | [next] | [standalone]

#8266

root <NoEMail@home.org> wrote:
>
> We'll see how the case currently running turns out. I only have to work
> out the solution for four or five cases then use that solution to
> unravel data for about 420 data sets.
>

I was surprised to find that only one solution exists to the problem.
I let the program run through all cases and it finished in a little
over 4 minutes. It ran through 3,486,784,401 (3.5B) cases.

I really don't like the results. I'll have to ponder that before
continuing.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming

csiph-web