CODEWITHSUNDEEP
algorithmsetsubset
user2631491
user2631491

Reputation:

Algorithm for counting n-element subsets of m-element set divisible by k

Suppose {1, 2, 3, ..., m} is a set. I choose n distinct elements from this set. Can I write an algorithm which counts the number of such subsets whose sum is divisible by k (ordering not mattering)?

This problem would have been much easier if ordering mattered, but it doesn't and I don't have a clue how to approach. Can anyone please help?

Upvotes: 0

Views: 1923

Answers (3)

Bruce Zu
Bruce Zu

Reputation: 507

it can work but slow

 /**
 * List all k  size subset of a given list with n unique elements.
 * n can be bigger than 64. this function will take O(K^N) time, Bad.
 *
 * @param list
 * @param subSetSize
 * @param subSet
 * @param indexFrom
 * @param indexEnd
 */
private static void subSetOf(List<Integer> list, int subSetSize, Set<Integer> subSet, int indexFrom, int indexEnd) {
    if (subSet == null) {
        assert 0 < subSetSize && subSetSize <= list.size();
        subSet = new HashSet(subSetSize);
    }
    if (subSetSize <= 64) {
        // Todo using bitwise trick
    }
    for (int index = indexFrom; index <= indexEnd; index++) {
        subSet.add(list.get(index));
        if (subSet.size() == subSetSize) {
            System.out.println(Arrays.toString(subSet.toArray()));
            // check the sum of this subset is satisfied or not by sum/k
        }
        if (subSet.size() < subSetSize) {
            subSetOf(list, subSetSize, subSet,
                    index + 1,
                    list.size() - (subSetSize - subSet.size()));
        }
        subSet.remove(list.get(index));
    }
}

public static void subSetOf(List<Integer> list,
                            int subSetSize,
                            Set<Integer> subSet) {
    subSetOf(list, subSetSize, subSet, 0, list.size() - subSetSize);
}

Upvotes: 0

Zolt&#225;n Haindrich
Zolt&#225;n Haindrich

Reputation: 1808

set -> all elements are different.

create an array to describe how many representatives each numberclass has:

ncnt=new int[k]
for x in elements{
  ncnt[x%k]++;
}

dynamic programming:

int waysToCreate(int input_class,int class_idx, int n){
  int ways=0
  // not using this class:
  if(class_idx+1 < k )
    ways+=waysToCreate(input_class,class_idx+1,n);
  for( int i=1;i < ncnt[class_idx] && i<=n ){
    int new_input_class=(input_class+i*class_idx)%k;
    if(i == n && new_input_class != 0){
      break; // all elements are used, but doesn't congrunent with 0 (mod k)
    }
    int subways=1;
    if(class_idx+1 < k )
      subways=waysToCreate(new_input_class,class_idx+1,n-i)

    ways+=nchoosek(ncnt[class_idx],i) * subways;
  }
  return ways;
}

enable memoize on waysToCreate, nchoosek

Upvotes: 0

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8701

This can be done in time O(n·k·m) and space O(n·k) by a method similar to that outlined below. Let S be your set with m elements. By definition of set and subset, all the elements of S are distinct, as are all the elements of any S-subset.

First, consider the simpler problem where we count S-subsets with any number of elements instead of exactly n elements. Let N(W,r) be the number of W-subsets U such that ΣU (the sum of elements of U) is equal to r mod k. If W is a subset of S, let W' be W + z, where z ∈ S\W; that is, z is an element of S not already in W. Now N(W', (r+z)%k) = N(W, (r+z)%k) + N(W, r) because N(W, (r+z)%k) is the number of W'-subsets U with ΣU≡(r+z)%k) that don't contain z and N(W, r) is the number of W'-subsets U with ΣU≡(r+z)%k) that do contain z. Repeat this construction, treating each element of S in turn until W' = S, at which point the desired answer is N(S,0). Time is O(k·m), space is O(k).

To adapt the above process for exact subset sizes, change N(W,r) to N(W,h,r), where h is a subset size, and adapt the equations for N(W',r) to N(W',h,r) in the obvious way. Time is O(k·n·m), space is O(k·n).

Upvotes: 2

Related Questions