Optimizing the implementation of a subset of sums
I am working on a solution to a variant of the subset sum problem using the code below. The problem has to do with creating subsets of 11 ints from a larger set (superset) and checking if it matches a certain value (endum).
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
int endsum = 0, supersetsize = 0, done = 0;
int superset[] = {1,30,10,7,11,27,3,5,6,50,45,32,25,67,13,37,19,52,18,9};
int combo = 0;
int searchForPlayerInArray(int arr[], int player) {
for (int i=0; i<11; i++) {
if (arr[i] == player) {
return 1;
}
}
return 0;
}
int sumOfArray(int arr[]) {
int res = 0;
for (int i=0; i<11; i++) {
res+=arr[i];
}
return res;
}
void printArray(int arr[], int arrSize) {
for (int j=0; j<arrSize; j++) {
printf("%2d ",arr[j]);
}
printf("= %d\n",endsum);
}
void permute(int subset[], int pos, int sspos) {
if (done) { //when a correct solution has been found, stop recursion
return;
}
if (sspos == supersetsize) { // out of possible additions
return;
}
if (pos == 11) { //is the current subset 11 ints long?
int res = sumOfArray(subset);
combo++;
if (res == endsum) { //if the sum of the array matches the wanted sum, print
printArray(subset,11);
done = 1;
}
return;
}
for (int i=sspos; i<supersetsize; i++) {
//assert(pos < 11);
//assert(i+1 <= supersetsize);
subset[pos] = superset[i];
permute(subset,pos+1,i+1);
}
}
int main(void) {
endsum = 110;
supersetsize = 20;
int *arr;
arr = malloc(supersetsize*sizeof(int));
int i;
for (i=0; i<supersetsize; i++) {
arr[i] = 0;
}
permute(arr,0,0);
printf("Combinations: %d",combo);
return 0;
}
While this solution works for small supersets (<15), it is slow and inefficient as it generates all possible permutations, not just unique ones. How can I optimize it to only create unique subsets?
Edit: The complete source code has been added per popular request.
source to share
One way to generate unique subsets is to order the elements from the superset and use an additional argument permute
(eg. supersetPos
) To indicate where you are in the superset. This creates sorted permutations that are unique.
EDIT : code that AFAIK works correctly on your sample:
#include <stdio.h>
int superset[] = {
1, 30, 10, 7, 11,
27, 3, 5, 6, 50,
45, 32, 25, 67, 13,
37, 19, 52, 18, 9
};
int supersetsize = 20;
int endsum = 110;
int done = 0;
int sumOfArray(int array[]) {
int sum = 0;
for(int i = 0; i < 11; i++)
sum += array[i];
return sum;
}
void permute(int subset[], int pos, int sspos) {
if (pos == 11) { //is the current subset 11 ints long?
if (sumOfArray(subset) == endsum) { //if the sum of the array matches the wanted sum, print
for (int j=0; j<11; j++) {
printf("%d ",subset[j]);
}
printf("\n");
done = 1;
}
return;
}
for (int i=sspos; i<supersetsize; i++) {
subset[pos] = superset[i];
permute(subset,pos+1,i+1);
if (done) { //when a correct solution has been found, stop recursion
return;
}
}
}
int main() {
int subset[11] = {0};
permute(subset, 0, 0);
}
source to share
I don't think there is a better way to generate unique subsets than exponential time.
To solve a subset efficiently, you want to use dynamic programming. There are some pseudo-polynomial time algorithms for a subset that work this way. This Wikipedia article can help.
source to share
you can try my code (I was trying to only give psudo code, not completely solve your homework):
// array is all the numbers you are looking from them
// length is the number of arrays
// pos is the position of the slot you are going to fill
// max is nomber of slots you have to fill (in your case since you are going for the 11 sets you have to set this value as 11
// sum is the sum of all the values selected until now
// searchbegin is the first element you can pick from your array (I'm using this variable to only generate subarrays of the superset (array))
// target is the targetvalue you are looking for.
void generate_all(int []array, int length, int pos,int max, int sum,int searchbegin,int target)
{
if max = pos
if sum = target
printselectedresults();
for i:searchbegin->length-max+pos
if (sum + array[i] < target)
{
addtoresults(i);
generate_all(array,length,pos+1,max,sum+array[i],i+1,target);
removefromresults(i);
}
}
with all this information, I think you can easily implement this code in your target language and use it.
in my function, all the generated permutations are subarrays of the superset, so no permutation can be generated twice, and also each one is generated at least once.
source to share