Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: bplus on September 08, 2020, 02:09:51 pm

Title: Ordered Combinations Generator
Post by: 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]
  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
  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
  47.  
  48. FOR i = 0 TO N
  49.     tot = tot + Counts(i)
  50.     PRINT Counts(i); ": "; subsets$(i)
  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)
  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
  79.  
  80.  

Title: Re: Ordered Combinations Generator
Post by: DANILIN 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:

 
Title: Re: Ordered Combinations Generator
Post by: bplus 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.
Title: Re: Ordered Combinations Generator
Post by: Rubidium on October 06, 2020, 07:18:30 pm
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)
  7.  
  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.  
  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.
Title: Re: Ordered Combinations Generator
Post by: bplus 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 :)
Title: Re: Ordered Combinations Generator
Post by: Rubidium on October 06, 2020, 07:43:37 pm
I didn't until I read your post :)

It's amazing how that works out.
Title: Re: Ordered Combinations Generator
Post by: bplus 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]
  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
  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
  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
  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.

Title: Re: Ordered Combinations Generator
Post by: STxAxTIC 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?
Title: Re: Ordered Combinations Generator
Post by: bplus 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.
Title: Re: Ordered Combinations Generator
Post by: STxAxTIC 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...
Title: Re: Ordered Combinations Generator
Post by: bplus on October 15, 2020, 09:26:27 pm
Yeah business has been gambling scientifically for centuries.
Text Only | Text with Attachments