Ordered Combinations Generator

[bplus]

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

Code: QB64: [Select]

1. OPTION _EXPLICIT
2. _TITLE "Generate all the combination subsets of an n element set" ' b+ 2020-09-08
3. DEFLNG A-Z
4. DIM set$, N, j, i, idx, L$, k, tot, test$
5. ' we will use letters to represent each element of the set
6. set$ = "abcdefg" ' for starters try a 7 element set
7.  
8. N = LEN(set$)
9. 'should be 2^n sets of combinations
10. DIM subsets$(0 TO N), Counts(0 TO N)
11.  
12. 'designate the empty set as *
13. subsets$(0) = "*"
14. Counts(0) = 1
15. ' the single element sets
16. FOR j = 1 TO N
17.     IF j = 1 THEN
18.         subsets$(1) = MID$(set$, j, 1)
19.     ELSE
20.         subsets$(1) = subsets$(1) + "," + MID$(set$, j, 1)
21.     END IF
22. NEXT
23. Counts(1) = N
24. FOR i = 2 TO N ' number of elements
25.     REDIM iM$(1)
26.     idx = 0
27.     Split subsets$(i - 1), ",", iM$()
28.     'try to add the jth element to the i-1 subset to make a subset of i elements
29.     FOR j = 1 TO N
30.         L$ = MID$(set$, j, 1)
31.         FOR k = j TO UBOUND(iM$)
32.             IF INSTR(iM$(k), L$) = 0 THEN ' make a new set of i elements
33.                 test$ = sorted$(iM$(k), L$)
34.                 IF INSTR(subsets$(i), test$) = 0 THEN 'not added yet
35.                     idx = idx + 1
36.                     IF idx = 1 THEN
37.                         subsets$(i) = test$
38.                     ELSE
39.                         subsets$(i) = subsets$(i) + "," + test$
40.                     END IF
41.                 END IF
42.             END IF
43.         NEXT
44.         Counts(i) = idx
45.     NEXT
46. NEXT
47.  
48. FOR i = 0 TO N
49.     tot = tot + Counts(i)
50.     PRINT Counts(i); ": "; subsets$(i)
51. NEXT
52. PRINT tot; " total subsets when N ="; N
53.  
54. FUNCTION sorted$ (sort$, L$)
55.     DIM i, m$, b$, added
56.     FOR i = 1 TO LEN(sort$)
57.         IF L$ < MID$(sort$, i, 1) THEN EXIT FOR
58.     NEXT
59.     sorted$ = MID$(sort$, 1, i - 1) + L$ + MID$(sort$, i)
60. END FUNCTION
61.  
62. 'notes: REDIM the array(0) to be loaded before calling Split '<<<< IMPORTANT dynamic array and empty, can use any lbound though
63. '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.
64. '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
65. SUB Split (SplitMeString AS STRING, delim AS STRING, loadMeArray() AS STRING)
66.     DIM curpos AS LONG, arrpos AS LONG, LD AS LONG, dpos AS LONG 'fix use the Lbound the array already has
67.     curpos = 1: arrpos = LBOUND(loadMeArray): LD = LEN(delim)
68.     dpos = INSTR(curpos, SplitMeString, delim)
69.     DO UNTIL dpos = 0
70.         loadMeArray(arrpos) = MID$(SplitMeString, curpos, dpos - curpos)
71.         arrpos = arrpos + 1
72.         IF arrpos > UBOUND(loadMeArray) THEN REDIM _PRESERVE loadMeArray(LBOUND(loadMeArray) TO UBOUND(loadMeArray) + 1000) AS STRING
73.         curpos = dpos + LD
74.         dpos = INSTR(curpos, SplitMeString, delim)
75.     LOOP
76.     loadMeArray(arrpos) = MID$(SplitMeString, curpos)
77.     REDIM _PRESERVE loadMeArray(LBOUND(loadMeArray) TO arrpos) AS STRING 'get the ubound correct
78. END SUB
79.  
80.  

[DANILIN]

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]

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]

Code: QB64: [Select]

1. DIM q(20) AS _UNSIGNED INTEGER 'index digit holders
2. DIM A$(26) 'sample space of the alphabet
3.  
4. FOR i = 1 TO 26 'create an alphabet deck of cards A$()
5.     A$(i) = CHR$(64 + i)
6. NEXT i
7.  
8. CLS
9.  
10. n = 7 'number of different characters to use
11. u = 1 ' initialize by choosing 1 of n characters skipping the combination of nothing 7 C 0
12.  
13. PRINT "CHARACTERS n:"; n
14. OPEN "combination_space.csv" FOR OUTPUT AS #1
15.  
16. DO
17.     'combination counter
18.     q(1) = q(1) + 1
19.  
20.     IF q(1) > n THEN
21.         FOR i = 1 TO u 'as in nCu: where u is the current number of "digits"
22.             IF q(i) > n - i + 1 THEN 'digit combination limit
23.                 q(i + 1) = q(i + 1) + 1
24.                 FOR k = (i) TO 1 STEP -1
25.                     q(k) = q(k + 1) + 1
26.                 NEXT k
27.                 IF i = u THEN u = u + 1
28.             END IF
29.         NEXT i
30.     END IF
31.  
32.     '// BELOW IS JUST FOR DISPLAY
33.     S$ = ""
34.     PRINT #1, " ,";
35.     FOR i = 1 TO u
36.         PRINT "["; RIGHT$(STR$(u - i + 1), 1); "]";
37.         PRINT #1, "q["; RIGHT$(STR$(u - i + 1), 1); "],";
38.     NEXT i
39.     PRINT #1, ""
40.     PRINT
41.  
42.  
43.     FOR i = 1 TO u
44.         S$ = A$(q(i)) + S$
45.         PRINT q(u - i + 1);
46.     NEXT i
47.     PRINT #1, S$; ",";
48.     FOR i = 1 TO u
49.         PRINT #1, q(u - i + 1); ",";
50.     NEXT i
51.  
52.     PRINT " = "; S$
53.  
54.     PRINT #1, ""
55.     PRINT #1, ""
56.     PRINT
57.     SLEEP
58. LOOP UNTIL u = n
59. PRINT "COMPLETED TOTAL COMBOS"
60.  
61.  

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

[bplus]

@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]

I didn't until I read your post :)

It's amazing how that works out.

[bplus]

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

Code: QB64: [Select]

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

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]

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]

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]

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]

Yeah business has been gambling scientifically for centuries.