Permutations of length #i#:
#ArrayToList(res[i])#
[allowsmilie] => 1 [showsignature] => 0 [ipaddress] => [iconid] => 0 [visible] => 1 [attach] => 0 [infraction] => 0 [reportthreadid] => 0 [isusenetpost] => 1 [msgid] => [ref] => [htmlstate] => on_nl2br [postusername] => Mr [ip] => webforumsuser@m [isdeleted] => 0 [usergroupid] => [membergroupids] => [displaygroupid] => [password] => [passworddate] => [email] => [styleid] => [parentemail] => [homepage] => [icq] => [aim] => [yahoo] => [msn] => [skype] => [showvbcode] => [showbirthday] => [usertitle] => [customtitle] => [joindate] => [daysprune] => [lastvisit] => [lastactivity] => [lastpost] => [lastpostid] => [posts] => [reputation] => [reputationlevelid] => [timezoneoffset] => [pmpopup] => [avatarid] => [avatarrevision] => [profilepicrevision] => [sigpicrevision] => [options] => [akvbghsfs_optionsfield] => [birthday] => [birthday_search] => [maxposts] => [startofweek] => [referrerid] => [languageid] => [emailstamp] => [threadedmode] => [autosubscribe] => [pmtotal] => [pmunread] => [salt] => [ipoints] => [infractions] => [warnings] => [infractiongroupids] => [infractiongroupid] => [adminoptions] => [profilevisits] => [friendcount] => [friendreqcount] => [vmunreadcount] => [vmmoderatedcount] => [socgroupinvitecount] => [socgroupreqcount] => [pcunreadcount] => [pcmoderatedcount] => [gmmoderatedcount] => [assetposthash] => [fbuserid] => [fbjoindate] => [fbname] => [logintype] => [fbaccesstoken] => [newrepcount] => [vbseo_likes_in] => [vbseo_likes_out] => [vbseo_likes_unread] => [temp] => [field1] => [field2] => [field3] => [field4] => [field5] => [subfolders] => [pmfolders] => [buddylist] => [ignorelist] => [signature] => [searchprefs] => [rank] => [icontitle] => [iconpath] => [avatarpath] => [hascustomavatar] => 0 [avatardateline] => [avwidth] => [avheight] => [edit_userid] => [edit_username] => [edit_dateline] => [edit_reason] => [hashistory] => [pagetext_html] => [hasimages] => [signatureparsed] => [sighasimages] => [sigpic] => [sigpicdateline] => [sigpicwidth] => [sigpicheight] => [postcount] => 2 [islastshown] => [isfirstshown] => [attachments] => [allattachments] => ) --> List combination - Coldfusion - Advanced Techniques

List combination - Coldfusion - Advanced Techniques

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: a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd. I appreciatie your help....

  1. #1

    Default 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:

    a,b,c,d,ab,ac,ad,bc,bd,cd,abc,abd,acd,bcd,abcd.

    I appreciatie your help.






    girmalemu Guest

  2. #2

    Default 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>

    Mr Guest

  3. #3

    Default 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.




    BKBK Guest

  4. #4

    Default 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.
    girmalemu Guest

  5. #5

    Default 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#">

    BKBK Guest

  6. #6

    Default 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.


    girmalemu Guest

  7. #7

    Default 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)#";}
    }
    }
    }

    BKBK Guest

Similar Threads

  1. Combination of formfields
    By Pascal_Kamperman@adobeforums.com in forum Adobe Acrobat Windows
    Replies: 2
    Last Post: May 3rd, 04:59 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •