Enumerate_Subsets.mws
Enumerating All Subsets of a Set
by Yufang Hao, <yhao@student.math.uwaterloo.ca>
This worksheet enumerates all subsets of a given set and computes the sum of each subset.
Lists are used instead of sets below, because order of the elements in a set is crucial in order to list all subsets without repetition..
sublist(list,ini)
pre: list is not empty, 1<=ini<=nops(list)
post: sub list containing elements from ini to nops(list) returns
> 
sublist := proc(list, ini)
[ seq(list[i],i=ini..nops(list)) ]:
end proc:

addElt(elt,list)
pre: elt is any valid element, and the argument 'list' is a list of lists
post: elt is added at the begining of each element(which is a list) in the argument 'list'.
> 
addElt := proc(elt, list)
local templist, i:
templist:=[]:
for i from 1 to nops(list) do
templist:=[ op(templist), [elt, op(list[i])] ]:
end do:
templist:
end proc:

> 
addElt(m, [[1,a],[2],[3,b,c],[4,d,x,y,x],[]]);

> 
addElt(a, [[b,c],[b,d],[c,d]]);

listSubsets(L,i)
pre: L is a nonempty list, 1<=i<=nops(L)
post: return a list of all possible subsets (sublists) of L with i elements
> 
listSubsets := proc(L, i)
local n, j, fl, temp: # flfinal list
n := nops(L):
if i=1 then # base case
fl:=[]:
for j from 1 to n do
fl:=[op(fl),[L[j]]]:
end do:
else
fl:=[]:
for j from 1 to ni+1 do
temp:=listSubsets(sublist(L,j+1),i1):
temp:=addElt(L[j],temp):
fl:=[op(fl),op(temp)]:
end do:
end if:
fl:
end proc:

> 
listSubsets([a,b,c,d,e,f,g],1);

> 
listSubsets([a,b,c,d,e,f,g],2);

> 
listSubsets([a,b,c,d,e,f,g],4);

listAllSubsets(L)
pre: L is a nonempty list
post: return a list of all possible subsets (sublists) of L (empty set or null set is excluded)
> 
listAllSubsets := proc(L)
local n, i, temp, fl:
n := nops(L):
fl := []:
for i from 1 to n do
fl:=[op(fl),op(listSubsets(L,i))]:
end do:
fl:
end proc:

> 
listAllSubsets([x,y,z]);

Excluding the empty set, there should be
subsets:
> 
nops(listAllSubsets([a,b,c,d,e,f,g,h])) = 2^nops([a,b,c,d,e,f,g,h])1;

> 
listAllSubsets([a,b,c,d,e,f,g,h]);

Mathematical Proof and Algorithm
Starting with the following combination formula, we could notice a recursive pattern:
Let (n,i) be the combination of n objects taken i at a time.
then we know (n,i)=(n1,i1)+(n1,i),
and apply this formula again on (n1,i), we have (n1,i)=(n2,i1)+(n1,i),
and continue recursively applying this formula, we eventually have:
(n,i) = (n1,i1) + (n2,i1) + (n3,i1) + (n4,i1) + ... + (i, i1) + (i,i)
and (i,i)=1=(i1,i1), so (n,i)=(n1,i1) + (n2,i1) + (n3,i1) + (n4,i1) + ... + (i, i1) + (i1,i1)
note the sizes of both n and i descrease, so a recrusive formula can be applied.
The algorithm to list all subsets with i elements of L is:
for first element, and combine it with any possible i1 elements chosen from any element safter first one in L, which is combine with all possible subsets with i1 elements in the set L(from 2 to n), there are totally (n1,i1) ways to select:
1st element + listSubsets(subset(L,2), i1);
then for second element, combine it with any possible i1 elements chosen from any elements after second one in L, which is to combine with all possible subsets with i1 elements in the set L(from 2 to n), there are totally (n2,i1) ways to pick:
2nd element + listSubsets(subset(L,3, i1);
......
for jth element, combine it with any possible i1 elements chosen from any elements after this jth element in L, which is to combine with all possible subsets with i1 elements in the set L(from j+1 to n), there are totally (nj,i1) ways to pick:
jst element + listSubsets(subset(L,j+1), i1);
.......
continue until the ni+1 element is reached, which left only one way (i1,i1) way to choose:
And all those combinations form all the possible subsets with i elements of L.
because 'i' decreases by 1 everytime, and 'i' is positive, it eventually reaches 1, which is the base case.
printAllSubsets(L)
pre: L is a nonempty list
post: print out all possible subsets (sublists) of L (empty set or null set is excluded)
> 
printAllSubsets := proc(L)
local list,i:
list:=listAllSubsets(L):
for i from 1 to nops(list) do
lprint(list[i]):
end do:
return NULL:
end proc:

> 
printAllSubsets([a,b,c,d]);

[a]
[b]
[c]
[d]
[a, b]
[a, c]
[a, d]
[b, c]
[b, d]
[c, d]
[a, b, c]
[a, b, d]
[a, c, d]
[b, c, d]
[a, b, c, d]
printAllSubsetSums(L)
pre: L is a nonempty list contains number elements
post: print out all possible subsets (sublists) of L (empty set or null set is excluded) and the sum of the numbers in each subset
> 
printAllSubsetSums := proc(L)
local list,i,sublist:
list:=listAllSubsets(L):
for i from 1 to nops(list) do
sublist:=list[i]:
lprint( sublist = sum(sublist['k'],'k'=1..nops(sublist)) ):
end do:
return NULL:
end proc:

> 
printAllSubsetSums([1,2,3,4]);

[1] = 1
[2] = 2
[3] = 3
[4] = 4
[1, 2] = 3
[1, 3] = 4
[1, 4] = 5
[2, 3] = 5
[2, 4] = 6
[3, 4] = 7
[1, 2, 3] = 6
[1, 2, 4] = 7
[1, 3, 4] = 8
[2, 3, 4] = 9
[1, 2, 3, 4] = 10
> 
printAllSubsetSums([1,2,4,8,16,32,61,127]);

[1] = 1
[2] = 2
[4] = 4
[8] = 8
[16] = 16
[32] = 32
[61] = 61
[127] = 127
[1, 2] = 1
[1, 4] = 5
[1, 8] = 7
[1, 16] = 17
[1, 32] = 31
[1, 61] = 62
[1, 127] = 128
[2, 4] = 2
[2, 8] = 10
[2, 16] = 14
[2, 32] = 34
[2, 61] = 59
[2, 127] = 125
[4, 8] = 4
[4, 16] = 20
[4, 32] = 28
[4, 61] = 65
[4, 127] = 131
[8, 16] = 8
[8, 32] = 40
[8, 61] = 53
[8, 127] = 119
[16, 32] = 16
[16, 61] = 77
[16, 127] = 143
[32, 61] = 29
[32, 127] = 95
[61, 127] = 188
[1, 2, 4] = 3
[1, 2, 8] = 9
[1, 2, 16] = 15
[1, 2, 32] = 33
[1, 2, 61] = 60
[1, 2, 127] = 126
[1, 4, 8] = 3
[1, 4, 16] = 21
[1, 4, 32] = 27
[1, 4, 61] = 66
[1, 4, 127] = 132
[1, 8, 16] = 9
[1, 8, 32] = 39
[1, 8, 61] = 54
[1, 8, 127] = 120
[1, 16, 32] = 15
[1, 16, 61] = 78
[1, 16, 127] = 144
[1, 32, 61] = 30
[1, 32, 127] = 96
[1, 61, 127] = 189
[2, 4, 8] = 6
[2, 4, 16] = 18
[2, 4, 32] = 30
[2, 4, 61] = 63
[2, 4, 127] = 129
[2, 8, 16] = 6
[2, 8, 32] = 42
[2, 8, 61] = 51
[2, 8, 127] = 117
[2, 16, 32] = 18
[2, 16, 61] = 75
[2, 16, 127] = 141
[2, 32, 61] = 27
[2, 32, 127] = 93
[2, 61, 127] = 186
[4, 8, 16] = 12
[4, 8, 32] = 36
[4, 8, 61] = 57
[4, 8, 127] = 123
[4, 16, 32] = 12
[4, 16, 61] = 81
[4, 16, 127] = 147
[4, 32, 61] = 33
[4, 32, 127] = 99
[4, 61, 127] = 192
[8, 16, 32] = 24
[8, 16, 61] = 69
[8, 16, 127] = 135
[8, 32, 61] = 21
[8, 32, 127] = 87
[8, 61, 127] = 180
[16, 32, 61] = 45
[16, 32, 127] = 111
[16, 61, 127] = 204
[32, 61, 127] = 156
[1, 2, 4, 8] = 5
[1, 2, 4, 16] = 19
[1, 2, 4, 32] = 29
[1, 2, 4, 61] = 64
[1, 2, 4, 127] = 130
[1, 2, 8, 16] = 7
[1, 2, 8, 32] = 41
[1, 2, 8, 61] = 52
[1, 2, 8, 127] = 118
[1, 2, 16, 32] = 17
[1, 2, 16, 61] = 76
[1, 2, 16, 127] = 142
[1, 2, 32, 61] = 28
[1, 2, 32, 127] = 94
[1, 2, 61, 127] = 187
[1, 4, 8, 16] = 13
[1, 4, 8, 32] = 35
[1, 4, 8, 61] = 58
[1, 4, 8, 127] = 124
[1, 4, 16, 32] = 11
[1, 4, 16, 61] = 82
[1, 4, 16, 127] = 148
[1, 4, 32, 61] = 34
[1, 4, 32, 127] = 100
[1, 4, 61, 127] = 193
[1, 8, 16, 32] = 23
[1, 8, 16, 61] = 70
[1, 8, 16, 127] = 136
[1, 8, 32, 61] = 22
[1, 8, 32, 127] = 88
[1, 8, 61, 127] = 181
[1, 16, 32, 61] = 46
[1, 16, 32, 127] = 112
[1, 16, 61, 127] = 205
[1, 32, 61, 127] = 157
[2, 4, 8, 16] = 10
[2, 4, 8, 32] = 38
[2, 4, 8, 61] = 55
[2, 4, 8, 127] = 121
[2, 4, 16, 32] = 14
[2, 4, 16, 61] = 79
[2, 4, 16, 127] = 145
[2, 4, 32, 61] = 31
[2, 4, 32, 127] = 97
[2, 4, 61, 127] = 190
[2, 8, 16, 32] = 26
[2, 8, 16, 61] = 67
[2, 8, 16, 127] = 133
[2, 8, 32, 61] = 19
[2, 8, 32, 127] = 85
[2, 8, 61, 127] = 178
[2, 16, 32, 61] = 43
[2, 16, 32, 127] = 109
[2, 16, 61, 127] = 202
[2, 32, 61, 127] = 154
[4, 8, 16, 32] = 20
[4, 8, 16, 61] = 73
[4, 8, 16, 127] = 139
[4, 8, 32, 61] = 25
[4, 8, 32, 127] = 91
[4, 8, 61, 127] = 184
[4, 16, 32, 61] = 49
[4, 16, 32, 127] = 115
[4, 16, 61, 127] = 208
[4, 32, 61, 127] = 160
[8, 16, 32, 61] = 37
[8, 16, 32, 127] = 103
[8, 16, 61, 127] = 196
[8, 32, 61, 127] = 148
[16, 32, 61, 127] = 172
[1, 2, 4, 8, 16] = 11
[1, 2, 4, 8, 32] = 37
[1, 2, 4, 8, 61] = 56
[1, 2, 4, 8, 127] = 122
[1, 2, 4, 16, 32] = 13
[1, 2, 4, 16, 61] = 80
[1, 2, 4, 16, 127] = 146
[1, 2, 4, 32, 61] = 32
[1, 2, 4, 32, 127] = 98
[1, 2, 4, 61, 127] = 191
[1, 2, 8, 16, 32] = 25
[1, 2, 8, 16, 61] = 68
[1, 2, 8, 16, 127] = 134
[1, 2, 8, 32, 61] = 20
[1, 2, 8, 32, 127] = 86
[1, 2, 8, 61, 127] = 179
[1, 2, 16, 32, 61] = 44
[1, 2, 16, 32, 127] = 110
[1, 2, 16, 61, 127] = 203
[1, 2, 32, 61, 127] = 155
[1, 4, 8, 16, 32] = 19
[1, 4, 8, 16, 61] = 74
[1, 4, 8, 16, 127] = 140
[1, 4, 8, 32, 61] = 26
[1, 4, 8, 32, 127] = 92
[1, 4, 8, 61, 127] = 185
[1, 4, 16, 32, 61] = 50
[1, 4, 16, 32, 127] = 116
[1, 4, 16, 61, 127] = 209
[1, 4, 32, 61, 127] = 161
[1, 8, 16, 32, 61] = 38
[1, 8, 16, 32, 127] = 104
[1, 8, 16, 61, 127] = 197
[1, 8, 32, 61, 127] = 149
[1, 16, 32, 61, 127] = 173
[2, 4, 8, 16, 32] = 22
[2, 4, 8, 16, 61] = 71
[2, 4, 8, 16, 127] = 137
[2, 4, 8, 32, 61] = 23
[2, 4, 8, 32, 127] = 89
[2, 4, 8, 61, 127] = 182
[2, 4, 16, 32, 61] = 47
[2, 4, 16, 32, 127] = 113
[2, 4, 16, 61, 127] = 206
[2, 4, 32, 61, 127] = 158
[2, 8, 16, 32, 61] = 35
[2, 8, 16, 32, 127] = 101
[2, 8, 16, 61, 127] = 194
[2, 8, 32, 61, 127] = 146
[2, 16, 32, 61, 127] = 170
[4, 8, 16, 32, 61] = 41
[4, 8, 16, 32, 127] = 107
[4, 8, 16, 61, 127] = 200
[4, 8, 32, 61, 127] = 152
[4, 16, 32, 61, 127] = 176
[8, 16, 32, 61, 127] = 164
[1, 2, 4, 8, 16, 32] = 21
[1, 2, 4, 8, 16, 61] = 72
[1, 2, 4, 8, 16, 127] = 138
[1, 2, 4, 8, 32, 61] = 24
[1, 2, 4, 8, 32, 127] = 90
[1, 2, 4, 8, 61, 127] = 183
[1, 2, 4, 16, 32, 61] = 48
[1, 2, 4, 16, 32, 127] = 114
[1, 2, 4, 16, 61, 127] = 207
[1, 2, 4, 32, 61, 127] = 159
[1, 2, 8, 16, 32, 61] = 36
[1, 2, 8, 16, 32, 127] = 102
[1, 2, 8, 16, 61, 127] = 195
[1, 2, 8, 32, 61, 127] = 147
[1, 2, 16, 32, 61, 127] = 171
[1, 4, 8, 16, 32, 61] = 42
[1, 4, 8, 16, 32, 127] = 108
[1, 4, 8, 16, 61, 127] = 201
[1, 4, 8, 32, 61, 127] = 153
[1, 4, 16, 32, 61, 127] = 177
[1, 8, 16, 32, 61, 127] = 165
[2, 4, 8, 16, 32, 61] = 39
[2, 4, 8, 16, 32, 127] = 105
[2, 4, 8, 16, 61, 127] = 198
[2, 4, 8, 32, 61, 127] = 150
[2, 4, 16, 32, 61, 127] = 174
[2, 8, 16, 32, 61, 127] = 162
[4, 8, 16, 32, 61, 127] = 168
[1, 2, 4, 8, 16, 32, 61] = 40
[1, 2, 4, 8, 16, 32, 127] = 106
[1, 2, 4, 8, 16, 61, 127] = 199
[1, 2, 4, 8, 32, 61, 127] = 151
[1, 2, 4, 16, 32, 61, 127] = 175
[1, 2, 8, 16, 32, 61, 127] = 163
[1, 4, 8, 16, 32, 61, 127] = 169
[2, 4, 8, 16, 32, 61, 127] = 166
[1, 2, 4, 8, 16, 32, 61, 127] = 167
> 
printAllSubsetSums([1,3,7,15,31,63,127]);

[1] = 1
[3] = 3
[7] = 7
[15] = 15
[31] = 31
[63] = 63
[127] = 127
[1, 3] = 4
[1, 7] = 8
[1, 15] = 16
[1, 31] = 32
[1, 63] = 64
[1, 127] = 128
[3, 7] = 10
[3, 15] = 18
[3, 31] = 34
[3, 63] = 66
[3, 127] = 130
[7, 15] = 22
[7, 31] = 38
[7, 63] = 70
[7, 127] = 134
[15, 31] = 46
[15, 63] = 78
[15, 127] = 142
[31, 63] = 94
[31, 127] = 158
[63, 127] = 190
[1, 3, 7] = 11
[1, 3, 15] = 19
[1, 3, 31] = 35
[1, 3, 63] = 67
[1, 3, 127] = 131
[1, 7, 15] = 23
[1, 7, 31] = 39
[1, 7, 63] = 71
[1, 7, 127] = 135
[1, 15, 31] = 47
[1, 15, 63] = 79
[1, 15, 127] = 143
[1, 31, 63] = 95
[1, 31, 127] = 159
[1, 63, 127] = 191
[3, 7, 15] = 25
[3, 7, 31] = 41
[3, 7, 63] = 73
[3, 7, 127] = 137
[3, 15, 31] = 49
[3, 15, 63] = 81
[3, 15, 127] = 145
[3, 31, 63] = 97
[3, 31, 127] = 161
[3, 63, 127] = 193
[7, 15, 31] = 53
[7, 15, 63] = 85
[7, 15, 127] = 149
[7, 31, 63] = 101
[7, 31, 127] = 165
[7, 63, 127] = 197
[15, 31, 63] = 109
[15, 31, 127] = 173
[15, 63, 127] = 205
[31, 63, 127] = 221
[1, 3, 7, 15] = 26
[1, 3, 7, 31] = 42
[1, 3, 7, 63] = 74
[1, 3, 7, 127] = 138
[1, 3, 15, 31] = 50
[1, 3, 15, 63] = 82
[1, 3, 15, 127] = 146
[1, 3, 31, 63] = 98
[1, 3, 31, 127] = 162
[1, 3, 63, 127] = 194
[1, 7, 15, 31] = 54
[1, 7, 15, 63] = 86
[1, 7, 15, 127] = 150
[1, 7, 31, 63] = 102
[1, 7, 31, 127] = 166
[1, 7, 63, 127] = 198
[1, 15, 31, 63] = 110
[1, 15, 31, 127] = 174
[1, 15, 63, 127] = 206
[1, 31, 63, 127] = 222
[3, 7, 15, 31] = 56
[3, 7, 15, 63] = 88
[3, 7, 15, 127] = 152
[3, 7, 31, 63] = 104
[3, 7, 31, 127] = 168
[3, 7, 63, 127] = 200
[3, 15, 31, 63] = 112
[3, 15, 31, 127] = 176
[3, 15, 63, 127] = 208
[3, 31, 63, 127] = 224
[7, 15, 31, 63] = 116
[7, 15, 31, 127] = 180
[7, 15, 63, 127] = 212
[7, 31, 63, 127] = 228
[15, 31, 63, 127] = 236
[1, 3, 7, 15, 31] = 57
[1, 3, 7, 15, 63] = 89
[1, 3, 7, 15, 127] = 153
[1, 3, 7, 31, 63] = 105
[1, 3, 7, 31, 127] = 169
[1, 3, 7, 63, 127] = 201
[1, 3, 15, 31, 63] = 113
[1, 3, 15, 31, 127] = 177
[1, 3, 15, 63, 127] = 209
[1, 3, 31, 63, 127] = 225
[1, 7, 15, 31, 63] = 117
[1, 7, 15, 31, 127] = 181
[1, 7, 15, 63, 127] = 213
[1, 7, 31, 63, 127] = 229
[1, 15, 31, 63, 127] = 237
[3, 7, 15, 31, 63] = 119
[3, 7, 15, 31, 127] = 183
[3, 7, 15, 63, 127] = 215
[3, 7, 31, 63, 127] = 231
[3, 15, 31, 63, 127] = 239
[7, 15, 31, 63, 127] = 243
[1, 3, 7, 15, 31, 63] = 120
[1, 3, 7, 15, 31, 127] = 184
[1, 3, 7, 15, 63, 127] = 216
[1, 3, 7, 31, 63, 127] = 232
[1, 3, 15, 31, 63, 127] = 240
[1, 7, 15, 31, 63, 127] = 244
[3, 7, 15, 31, 63, 127] = 246
[1, 3, 7, 15, 31, 63, 127] = 247
Summation of the sums of elements in all possible subsets
Let totalSum be the summation of the sums of the elements in all possible subsets.
getTotalSum(L)
pre: L is a nonempty list contains number elements
post: return the summation of the sums of elements in all possible subsets
> 
getTotalSum := proc(L)
local list,i,sublist,totalsum:
list:=listAllSubsets(L):
totalsum:=0:
for i from 1 to nops(list) do
sublist:=list[i]:
totalsum := totalsum+sum(sublist['k'],'k'=1..nops(sublist)):
end do:
return totalsum:
end proc:

> 
getTotalSum([1,2,4,8,16,32,61,127]);

> 
getTotalSum([1,3,7,15,31,63,127]);

The above procedure finds the totalSum by using loops and recursive functions. An alternative approach is as follows:
For all elements in all possible subsets, their distribution is uniform, (strictly speaking we should use term list, since no repeated elements can be in a set.) So we only need to find the total number of elements in all possible subsets, then divide by n, and multiply by the sum of the original given list/set. The same answers should be obtained.
> 
getTotalSum2 := proc(L)
local n:
n:=nops(L):
sum(i*binomial(n,i),i=1..n)/n*sum(L[i],i=1..n):
end proc:

> 
getTotalSum2([1,2,4,8,16,32,61,127]);

> 
getTotalSum2([1,3,7,15,31,63,127]);
