CODEWITHSUNDEEP
algorithmcombinatoricssubset-sum
sehrgut
sehrgut

Reputation: 210

Algorithm for generating a set of Subset-Distinct-Sum integers

I'm attempting to create a scoring system for a card game which would preclude ties in scoring, by setting the point value of each card such that no two combinations of cards could add up to the same score. (For this particular case, I need a set of 17 integers, since there are 17 scorable cards.)

I've tried several heuristic approaches (various winnowing procedures along the lines of taking an array of integers, iteratively generating random subsets, and discard those which appear in subsets sharing a common sum); then exhaustively validating the results (by enumerating their subsets).

From what I've seen, the theoretical limit to the size of such a set is near log2(n), where n is the number of members of the superset from which the subset-distinct-sum subset is drawn. However, while I've been able to approach this, I've not been able to match it. My best result so far is a set of 13 integers, drawn from the 250,000 integers between 10,000 and 25,000,000, counting by hundreds (the latter is immaterial to the algorithm, but is a domain constrain of my use case):

[332600,708900,2130500,2435900,5322500,7564200,10594500,12776200,17326700,17925700,22004400,23334700,24764900]

I've hunted around, and most of the SDS generators are sequence generators that make no pretense of creating dense sets, but instead have the ability to be continued indefinitely to larger and larger numbers (e.g. the Conway-Guy Sequence). I have no such constraint, and would prefer a denser set without requiring a sequence relationship with each other.

(I did consider using the Conway-Guy Sequence n=2..18 * 10,000, but the resulting set has a broader range than I would like. I'd also really like a more general algorithm.)

Edit: For clarity, I'm looking for a way (non-deterministic or dynamic-programming methods are fine) to generate an SDS set denser than those provided by simply enumerating exponents or using a sequence like Conway-Guy. I hope, by discarding the "sequence generator" constraint, I can find numbers much closer together than such sequences provide.

Upvotes: 1

Views: 1936

Answers (2)

RBarryYoung
RBarryYoung

Reputation: 56785

For any value of N, it is readily possible to generate up to Floor(Log2(N))-1 numbers (which we'll call the set "S") such that:

  1. All members of S are less than or equal to N, and

  2. No two distinct subsets of S have the same sum, and

  3. All members of S are within a factor of two of each other.

Your suspicions were correct in that S would not be in any sense extensible (you could not add more members to it)

Method:

  1. For N, find T = 2^P , where T is the highest power of two that is less than or equal to N. That is:

    • P = Floor( Log2(N) ), and
    • T = 2^P

  2. Then the members of S can be generated as:

    • for( i=0 to P-2 ): S(i) = 2^i + 2^(P-1)
    • Or, to put it another way, S(i) = 2^i, for 0<= i < P-1

This makes for a total of P-1 (or Floor(Log2(N))-1) members. Can two distinct subsets of S ever sum to the same number? No:

Proof

Let's consider any two subsets of S: U and V, which are distinct (that is, they have no members in common). Then the sum of U is:

Sum(U) = O(U)*(T/2) + Sum(2^i| S(i):U)

Where

  • O(U) is the Order of the set U (how many elements it has),
  • "S(i):U" means "S(i) is an element of U", and
  • "|" is the conditioning operator (means "given that.." or "where.."),

So, putting the last two together, Sum(2^i| S(i):U) just means "the sum of all of the powers of two that are elements of U" (remembering that S(i) = 2^i)).

And likewise, the sum of V is:

Sum(V) = O(V)*(2^(P-1)) + Sum(2^i| S(i):V)

Now because U and V are distinct: Sum(2^i| S(i):U) can never be equal, because no two sums of distinct powers of two can ever be equal.

Also, because Sum(2^i; 0 <= i < P-1) = 2^(P-1)-1), these sums of the powers of two must always be less than 2^P-1. This means that the sums of U and V could only be equal if:

O(U)*(2^(P-1)) = O(V)*(2^(P-1))

or

O(U) = O(V)

That is, if U and V have the same number of elements, so that the first terms will be equal (because the second terms can never be as large as any differences in the first terms).

In such a case (O(U) = (O(V)) the first terms are equal, so Sum(U) would equal Sum(V) IFF their second terms (the binary sums) are also equal. However, we already know that they can never be equal, therefore, it can never be true that Sum(U) = Sum(V).

Upvotes: 1

Mshnik
Mshnik

Reputation: 7042

It seems like another way of phrasing the problem is to make sure that the previous terms never sum to the current term. If that's never the case, you'll never have two sums that add up to the same.

Ex: 2, 3, 6, 12, 24, 48, 96, ...

Summing to any single element {i} takes 1 more than the sum of the previous terms, and summing to any multi-element set {i,j} takes more than the sum of previous elements to i and previous elements to j.

More mathematically: (i-1), i, 2i, 4i, 8i, ... 2^n i Should work for any i, n.

The only way this doesn't work is if you're allowed to choose the same number twice in your subset (if that's the case, you should specify it in the problem). But that brings up the issue that Sum{i} = Sum{i} for any number, so that seems like an issue.

Upvotes: 0

Related Questions