Author Topic: Ordered Combinations Generator (Read 2804 times)

bplus · « **on:** September 08, 2020, 02:09:51 pm »

An Ordered Combinations Generator is a beautiful thing :) (using letters to represent elements in a set)

Code: QB64: [Select]

OPTION _EXPLICIT
_TITLE "Generate all the combination subsets of an n element set" ' b+ 2020-09-08
DEFLNG A-Z
DIM set$, N, j, i, idx, L$, k, tot, test$
' we will use letters to represent each element of the set
set$ = "abcdefg" ' for starters try a 7 element set
 
N = LEN(set$)
'should be 2^n sets of combinations
DIM subsets$(0 TO N), Counts(0 TO N)
 
'designate the empty set as *
subsets$(0) = "*"
Counts(0) = 1
' the single element sets
FOR j = 1 TO N
    IF j = 1 THEN
        subsets$(1) = MID$(set$, j, 1)
    ELSE
        subsets$(1) = subsets$(1) + "," + MID$(set$, j, 1)
    END IF
NEXT
Counts(1) = N
FOR i = 2 TO N ' number of elements
    REDIM iM$(1)
    idx = 0
    Split subsets$(i - 1), ",", iM$()
    'try to add the jth element to the i-1 subset to make a subset of i elements
    FOR j = 1 TO N
        L$ = MID$(set$, j, 1)
        FOR k = j TO UBOUND(iM$)
            IF INSTR(iM$(k), L$) = 0 THEN ' make a new set of i elements
                test$ = sorted$(iM$(k), L$)
                IF INSTR(subsets$(i), test$) = 0 THEN 'not added yet
                    idx = idx + 1
                    IF idx = 1 THEN
                        subsets$(i) = test$
                    ELSE
                        subsets$(i) = subsets$(i) + "," + test$
                    END IF
                END IF
            END IF
        NEXT
        Counts(i) = idx
    NEXT
NEXT
 
FOR i = 0 TO N
    tot = tot + Counts(i)
    PRINT Counts(i); ": "; subsets$(i)
NEXT
PRINT tot; " total subsets when N ="; N
 
FUNCTION sorted$ (sort$, L$)
    DIM i, m$, b$, added
    FOR i = 1 TO LEN(sort$)
        IF L$ < MID$(sort$, i, 1) THEN EXIT FOR
    NEXT
    sorted$ = MID$(sort$, 1, i - 1) + L$ + MID$(sort$, i)
END FUNCTION
 
'notes: REDIM the array(0) to be loaded before calling Split '<<<< IMPORTANT dynamic array and empty, can use any lbound though
'This SUB will take a given N delimited string, and delimiter$ and create an array of N+1 strings using the LBOUND of the given dynamic array to load.
'notes: the loadMeArray() needs to be dynamic string array and will not change the LBOUND of the array it is given.  rev 2019-08-27
SUB Split (SplitMeString AS STRING, delim AS STRING, loadMeArray() AS STRING)
    DIM curpos AS LONG, arrpos AS LONG, LD AS LONG, dpos AS LONG 'fix use the Lbound the array already has
    curpos = 1: arrpos = LBOUND(loadMeArray): LD = LEN(delim)
    dpos = INSTR(curpos, SplitMeString, delim)
    DO UNTIL dpos = 0
        loadMeArray(arrpos) = MID$(SplitMeString, curpos, dpos - curpos)
        arrpos = arrpos + 1
        IF arrpos > UBOUND(loadMeArray) THEN REDIM _PRESERVE loadMeArray(LBOUND(loadMeArray) TO UBOUND(loadMeArray) + 1000) AS STRING
        curpos = dpos + LD
        dpos = INSTR(curpos, SplitMeString, delim)
    LOOP
    loadMeArray(arrpos) = MID$(SplitMeString, curpos)
    REDIM _PRESERVE loadMeArray(LBOUND(loadMeArray) TO arrpos) AS STRING 'get the ubound correct
END SUB
 
 

DANILIN · « **Reply #1 on:** September 08, 2020, 02:46:42 pm »

Formula for N digital is Sx combination

S2 = N*(N-1) / (1*2)
for N=5: S2 = 5*4/2 = 20/2 = 10

S3 = N*(N-1)*(N-2) / (1*2*3)
for N=5: S3 = 5*4*3/6 = 60/6 = 10

S4 = N*(N-1)*(N-2)*(N-3) / (1*2*3*4)
for N=5: S3 = 5*4*3*2/24 = 120/24 = 5

Visualization:

bplus · « **Reply #2 on:** September 08, 2020, 03:15:57 pm »

But for completely ordered sets specially in the subset of 1 element sets you must start with letters in order.

Here is example of disorder:

BTW who knew that the number of proper subsets of a set with N elements is 2^N? = number of all combinations you can make with N things.

Right, Pascal knew.

Rubidium · « **Reply #3 on:** October 06, 2020, 07:18:30 pm »

Code: QB64: [Select]

DIM q(20) AS _UNSIGNED INTEGER 'index digit holders
DIM A$(26) 'sample space of the alphabet
 
FOR i = 1 TO 26 'create an alphabet deck of cards A$()
    A$(i) = CHR$(64 + i)
NEXT i
 
CLS
 
n = 7 'number of different characters to use
u = 1 ' initialize by choosing 1 of n characters skipping the combination of nothing 7 C 0
 
PRINT "CHARACTERS n:"; n
OPEN "combination_space.csv" FOR OUTPUT AS #1
 
DO
    'combination counter
    q(1) = q(1) + 1
 
    IF q(1) > n THEN
        FOR i = 1 TO u 'as in nCu: where u is the current number of "digits"
            IF q(i) > n - i + 1 THEN 'digit combination limit
                q(i + 1) = q(i + 1) + 1
                FOR k = (i) TO 1 STEP -1
                    q(k) = q(k + 1) + 1
                NEXT k
                IF i = u THEN u = u + 1
            END IF
        NEXT i
    END IF
 
    '// BELOW IS JUST FOR DISPLAY
    S$ = ""
    PRINT #1, " ,";
    FOR i = 1 TO u
        PRINT "["; RIGHT$(STR$(u - i + 1), 1); "]";
        PRINT #1, "q["; RIGHT$(STR$(u - i + 1), 1); "],";
    NEXT i
    PRINT #1, ""
    PRINT
 
 
    FOR i = 1 TO u
        S$ = A$(q(i)) + S$
        PRINT q(u - i + 1);
    NEXT i
    PRINT #1, S$; ",";
    FOR i = 1 TO u
        PRINT #1, q(u - i + 1); ",";
    NEXT i
 
    PRINT " = "; S$
 
    PRINT #1, ""
    PRINT #1, ""
    PRINT
    SLEEP
LOOP UNTIL u = n
PRINT "COMPLETED TOTAL COMBOS"
 
 

I made a similar one too so I thought I'd post.

bplus · « **Reply #4 on:** October 06, 2020, 07:39:07 pm »

@Rubidium

Nice! welcome to the forum.

With the empty set, the number of subsets or combinations add up to 2^N where N = number of elements but maybe you know already :)

Rubidium · « **Reply #5 on:** October 06, 2020, 07:43:37 pm »

I didn't until I read your post :)

It's amazing how that works out.

bplus · « **Reply #6 on:** October 15, 2020, 12:22:19 pm »

This might be an even better way to get combination listings, eg don't need split and sort at all!

Code: QB64: [Select]

_TITLE "Simple method to generate combinations of n items" ' b+ 2020-10-15
 
' decisions: powers are base 0 so keep items$() array also base 0
' number of anything is usually base 1 so if we say number of items it would go from 1 to n
' but if we say topItemIndex we have a base 0 item count for accessing array wo errors.
' So call number of items base 1 >>> topIndex = nItems -1
 
DEFLNG A-Z
DO
    INPUT "Item to add to set for combos, nothing to end list "; item$
    IF item$ <> "" THEN 'item is not nothing
        nItems = nItems + 1 ' number is base 1
        items$(nItems - 1) = item$ 'add n-th item to 0 based array
        'increment the index and
        IF nItems + 1 > 10 THEN EXIT DO ' keep count at 10 or less so don't need to DIM an array
    ELSE
        EXIT DO
    END IF
LOOP
 
' generating listings of combos
topComboIndex = 2 ^ nItems - 1 ' base 0 array
FOR i = 0 TO topComboIndex ' just going to print but could make list in array or process combo immediately
    b$ = "" ' for building a combination
    FOR power = 0 TO nItems - 1
        IF i AND 2 ^ power THEN
            IF b$ = "" THEN b$ = items$(power) ELSE b$ = b$ + ", " + items$(power)
        END IF
    NEXT
    PRINT i + 1; "= "; b$, 'the combiunation built
NEXT
 

EDIT: previous code was working but it was confusing why. For sake of clarity like I might need to use this some time in future I renamed variables and reworked code around the count of how many items we will make combinations with. For n items you will get 2 ^ n combinations the first will be the empty set or nothing.

The conflict between base 1 stuff and base 0 stuff really gave me a headache today but I think I have it cleared now.

STxAxTIC · « **Reply #7 on:** October 15, 2020, 06:22:03 pm »

Not really adding much to the discussion, but this kind of thinking lends itself to some interesting --- notation? For lack of a better word.

Remember when we did the play problem of finding a secret message inside a jumble of random text? Steve and bplus had loops and INSTR based answers, but I went a weird statistical way, documented here:

http://wfbarnes.net/homedata/Ordo%20Ab%20Chao.pdf

Point is, the combination lists bplus is going after are what I called the phi-sequences. (When I get to a PC I'll actually run the code.)

Any direct application in mind so far?

bplus · « **Reply #8 on:** October 15, 2020, 07:20:11 pm »

Quote

Any direct application in mind so far?

I've used it in Knapsack problem from Rosetta Code when I learned my first approach will not work generally for such like problems, the combination approach does.
https://www.qb64.org/forum/index.php?topic=3091.msg124013#msg124013

Also used combinations to optimize a Gin Hand. When a card intersects a Straight set and a group set have to decide which set to use it because can't be used in both. So run through all combinations of using intersect cards in one set or the other and see which returns highest points and / or least deadwood.
https://www.qb64.org/forum/index.php?topic=2550.msg123905#msg123905

I intend to update my Gin Hand Optimizer code with this generator code to dump outside Combination Tables and do more conventional Gin Game variations.

STxAxTIC · « **Reply #9 on:** October 15, 2020, 08:12:36 pm »

This stuff is interesting - I just skimmed across an article earlier that was all about the end of "luck" in gambling, in that Han Solo kind of way - because we are so good nowadays at calculating probabilities on the fly - gambling and gaming in general is thick with applied science these days...

bplus · « **Reply #10 on:** October 15, 2020, 09:26:27 pm »

Yeah business has been gambling scientifically for centuries.

News:

Author Topic: Ordered Combinations Generator (Read 2804 times)

bplus

Ordered Combinations Generator

DANILIN

Re: Ordered Combinations Generator

bplus

Re: Ordered Combinations Generator

Rubidium

Re: Ordered Combinations Generator

bplus

Re: Ordered Combinations Generator

Rubidium

Re: Ordered Combinations Generator

bplus

Re: Ordered Combinations Generator

STxAxTIC

Re: Ordered Combinations Generator

bplus

Re: Ordered Combinations Generator

STxAxTIC

Re: Ordered Combinations Generator

bplus

Re: Ordered Combinations Generator