Re: counting subsets of S so that sum(S_n) = N
- From: Willem <willem@xxxxxxxx>
- Date: Tue, 27 Mar 2007 08:31:38 +0000 (UTC)
stdazi@xxxxxxxxx wrote:
)
) Logan Shaw je napisal:
)> azi.stdout@xxxxxxxxx wrote:
)> > Well, it's not really the NP completeness that bothers me, but rather
)> > my lame "subset" generation method.. Many "subsets" repeat over time
)> > so I have to keep track of already summed sets and check them each
)> > time I've encountered a "valid" subset.
)> >
)> > I'm wondering.. Is there really no elegant way to get rid of repeated
)> > subsets, and make my algorithm generate only unique subsets?
)>
)> I assume you're referring to cases like then one where S is (2, 3, 2, 5)
)
) S is a "proper" set, that is, it contains only unique elements. S_n,
) the set with the sum propriety is the one that can hold repeated
) values.
That can be transformed to the case with S not containing unique elements
and each element only being chosen once, simply by adding X copies of each
member of the set S, where X is such that (item*(X+1)) is larger than N.
As an example, if you have the set 2, 3, 5 and you want to sum to 12, then
you change it into the bag (2, 6) (3, 4) (5, 2) and run the algorithm that
Logan proposed. You can then, of course, improve upon that by dynamically
limiting the number of items during the algorithm.
Something like:
int size = 3;
int list[3] = {2, 3, 5};
int connts[3];
int total = 12;
void recurse(int index, int sum)
{
if (--index < 0)
return;
for (counts[index] = 0; sum < total; counts[index]++)
{
recurse(index, sum);
sum += list[index];
}
if (sum == total)
{
int i;
for (i = index; i < size; i++) {
if (counts[i] > 0)
printf("%d * %d, ", counts[i], list[i]);
}
printf("= %d", total);
}
}
void main()
{
recurse(size, 0);
}
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.
- Follow-Ups:
- Re: counting subsets of S so that sum(S_n) = N
- From: Richard Heathfield
- Re: counting subsets of S so that sum(S_n) = N
- References:
- counting subsets of S so that sum(S_n) = N
- From: stdazi@xxxxxxxxx
- Re: counting subsets of S so that sum(S_n) = N
- From: Chris Uppal
- Re: counting subsets of S so that sum(S_n) = N
- From: azi . stdout
- Re: counting subsets of S so that sum(S_n) = N
- From: Logan Shaw
- Re: counting subsets of S so that sum(S_n) = N
- From: stdazi@xxxxxxxxx
- counting subsets of S so that sum(S_n) = N
- Prev by Date: Re: counting subsets of S so that sum(S_n) = N
- Next by Date: Re: counting subsets of S so that sum(S_n) = N
- Previous by thread: Re: counting subsets of S so that sum(S_n) = N
- Next by thread: Re: counting subsets of S so that sum(S_n) = N
- Index(es):
Relevant Pages
|
