# List combination

• October 26th, 03:15 PM
girmalemu
List combination
Combination / Permutation question.

I have posted similar message in this forum but do not get the solution yet.
Now I put it in a different way. Say I have a list of four elements - a,b,c,d
<cfset list ="a,b,c,d">

I need all combinations among the list. The combined results should be unique:

• October 26th, 07:22 PM
Mr
Re: List combination
One of possible solutions:

<!--- Original list --->
<cfset list="a,b,c,d">

<!--- Convert to array to make life easier --->
<cfset list=ListToArray(list)>
<!--- Number of iterations --->
<cfset n=ArrayLen(list)-1>
<!--- Result --->
<cfset res=ArrayNew(2)>
<!--- Permutations of length 1 --->
<cfset res[1]=list>

<!--- n iterations --->
<cfloop index="i" from="1" to="#n#">
<!--- Next length: Outer product of res[i] and list --->
<cfset prod=ArrayNew(1)>
<cfloop index="j" from="1" to="#ArrayLen(res[i])#">
<cfloop index="k" from="1" to="#ArrayLen(list)#">
<cfset ArrayAppend(prod, "#res[i][j]##list[k]#")>
</cfloop>
</cfloop>
<!--- Append permutations of length i+1 --->
<cfset ArrayAppend(res, prod)>
</cfloop>

<!--- Display results --->
<cfoutput>
<cfloop index="i" from="1" to="#ArrayLen(res)#">
Permutations of length #i#:<br>
#ArrayToList(res[i])#<hr>
</cfloop>
</cfoutput>

• October 26th, 07:39 PM
BKBK
Re: List combination
>... Say I have a list of four elements - a,b,c,d <cfset list ="a,b,c,d">
unique:

What you seek is a listing of the non-empty subsets of a set.
Following your example, it is {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}
for the set {a,b,c,d}. This grows rapidly as the number of elements
in the set increases.

In fact a set of N elements has 2^N - 1 non-empty subsets, where the
caret symbol ^ stands for "to the power". Verify this using the
given example, which has 4 elements. You get 2^4 - 1 = 16 - 1 = 15.
Counting, we confirm that there indeed are 15 subsets. Before you go
into the details of the code, you should heed a warning contained in
the formula. For an even moderately large set, the number of non-empty
subsets can be very large. That might adversely affect performance.

In my opinion, the most straightforward, not necessarily the most
efficient, way of enumerating the subsets of a set is by so-called
lexicographic ordering . It is a big name for a small principle.
You will see why in a minute.

We want code that will work for a set that contains an arbitrary number
of elements, N. There is a clue in the above formula, namely, 2^N. In
lexicographic ordering, we work with powers of 2. Assume that N is 4 or more.

Write out one column consisting of 2^N entries, just 0s and 1s; the
first 2^(N-1) are all 0s and the next 2^(N-1) are all 1s. To illustrate,
if N is 4, as in the example above, then you will have a column of
2^3 zeros followed by 2^3 ones. That is, 8 zeros followed by 8 ones.

0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

In the second column, starting with the 0s, you write down alternately
2^(N-2) zeros and 2^(N-2) ones. With our 4-element set,
that would mean alternating between 2^2 zeros and 2^2 ones. That is, you
alternate between 4 zeros and 4 ones, starting with the zeros.

0 0
0 0
0 0
0 0
0 1
0 1
0 1
0 1
1 0
1 0
1 0
1 0
1 1
1 1
1 1
1 1

In the third column, again starting with the 0s, alternate between
2^(N-3) zeros and 2^(N-3) ones. With N=4, that means alternating between
2^1 zeros and 2^1 ones. That is, you alternate between 2 zeros and 2 ones,
starting with the zeros.

0 0 0
0 0 0
0 0 1
0 0 1
0 1 0
0 1 0
0 1 1
0 1 1
1 0 0
1 0 0
1 0 1
1 0 1
1 1 0
1 1 0
1 1 1
1 1 1

You should have noticed by now that, for each subsequent column, the number
of alternating 0s and 1s is halved. A lexicographic ordering is the name
given to the final result that you get when you continue this process until
you reach a column that contains an alternation of 1 zero and 1 one. That
is then the final column.

Lexicographic ordering for N=4

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

Lexicographic ordering for N=3

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Lexicographic ordering for N=5

00000 (A)
00001
00010
00011
00100 (B)
00101
00110
00111
01000
01001
01010
01011 (C)
01100
01101
01110
01111
10000
10001 (D)
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011 (E)
11100
11101
11110
11111 (F)

Take the example of N=5. Let's say our set or "list" is {a,b,c,d,e}.
The lexicographic ordering has 32 entries, that is, 32 rows. A zero
represents "no" and a one represents "yes". In each row, the position
of the 0 or 1 corresponds to an identical position in the set or list.
In this way the lexicographic ordering produces all the subsets of
the set.

Some subsets for N=5 (corresponding to the letters):

A Empty set
B {c}
C {b,d,e}
D {a,e}
E {a,b,d,e}
F {a,b,c,d,e}

And what has lexicographic ordering to do with our original problem?
It solves our problem completely! The algorithm part, that is. But that
was the difficult part. The Coldfusion code then follows easily.

• October 27th, 09:17 AM
girmalemu
Re: List combination
Thank you BKBK,

I will appreciate if you attach code that produces:

A
B
C
AB
AC
BC
ABC

For a list = A,B,C

Thanks again.
• October 27th, 11:13 AM
BKBK
Re: List combination
Using exactly the same arguments, you can easily extend this yourself to
{a,b,c,d}, {a,b,c,d,e}, etc.

<cfscript>
ordering = ArrayNew(1);
subset = ArrayNew(1);
dummyVar = ArraySet(subset,1,7,"");
ordering[1]="0,0,1";
ordering[2]="0,1,0";
ordering[3]="0,1,1";
ordering[4]="1,0,0";
ordering[5]="1,0,1";
ordering[6]="1,1,0";
ordering[7]="1,1,1";
set = "a,b,c";
for (i=1; i LTE 7; i=i+1) {
for (j=1; j LTE 3; j=j+1) {
if (ListGetAt(ordering[i],j)) {
if(Len(subset[i]) EQ 0){subset[i]="#ListGetAt(set,j)#";}
else {subset[i]=subset[i]&","&"#ListGetAt(set,j)#";}
}
}
}
</cfscript>
<cfdump var="#subset#">

• October 27th, 05:25 PM
girmalemu
Re: List combination
BKBK thank you, This is what i wanted. May I ask you one more question?
Is there a way to apply it in dynamic lists, i.e. the list is database driven and varies in number from 2 to 12.

• October 28th, 10:56 AM
BKBK
Re: List combination
Is there a way to apply it in dynamic lists, i.e. the list is database driven
and varies in number from 2 to 12.
Yeah, sure. There, indeed, lies the power of the lexicographic ordering.

For example, a component comes to mind. It will have two methods. The first
one takes just one argument, an integer N; it performs a lexicographic ordering
of order N and returns an array containing the 2^N elements of the ordering.

The second method accepts an array. Its code is essentially the one I've given
above. That is, something along the lines of

M = 2^N - 1;
for (i=1; i LTE M; i=i+1) {
for (j=1; j LTE N; j=j+1) {
if (ListGetAt(ordering[i],j)) {
if(Len(subset[i]) EQ 0){subset[i]="#ListGetAt(set,j)#";}
else {subset[i]=subset[i]&","&"#ListGetAt(set,j)#";}
}
}
}