Lazarus

Programming => General => Topic started by: embedded-systems on December 22, 2024, 07:16:57 pm

Title: Algoritm for combination of numbers
Post by: embedded-systems on December 22, 2024, 07:16:57 pm
Hello all,
I am programming a simple task game for 7 players and my question is more about algorithm than programming...
I have defined:

Code: Pascal  [Select][+][-]
  1. var Myarray array[0..30] of Byte;   // source data
  2. var ArrayLength : Byte;
  3.  
  4. type DataResult = record     // result data
  5.                          n1: byte;
  6.                          n2: byte;
  7.                          n3: byte;
  8.                          n4: byte;
  9.                          n5: byte;
  10.                          n6: byte;
  11.                          n7: byte;
  12.                       end;      
  13.  
  14. var ResultArray : array[0..100000] of DataResult;

Can you recommend me the best algorithm to generate all 7 combinations of numbers (number must not repeat, order is not important) from the numbers that are in Myarray at positions 1 to ArrayLength into ResultArray?

The easiest way I have tried is "brute force" :

Code: Pascal  [Select][+][-]
  1. mycount:=0;
  2.    
  3.     for a1:=1 to ArrayLength-6 do
  4.       for a2:=2 to ArrayLength-5 do
  5.         for a3:=3 to ArrayLength-4 do
  6.           for a4:=4 to ArrayLength-3 do
  7.             for a5:=5 to ArrayLength-2 do
  8.               for a6:=6 to ArrayLength-1 do
  9.                 for a7:=7 to ArrayLength do
  10.                   begin
  11.                         inc(mycount);
  12.                         ResultArray[mycount].n1:=Myarray[a1];
  13.                         ResultArray[mycount].n2:=Myarray[a2];
  14.                         ResultArray[mycount].n3:=Myarray[a3];
  15.                         ResultArray[mycount].n4:=Myarray[a4];
  16.                         ResultArray[mycount].n5:=Myarray[a5];
  17.                         ResultArray[mycount].n6:=Myarray[a6];
  18.                         ResultArray[mycount].n7:=Myarray[a7];
  19.                  end;

In principle it works, but it is very slow because it generates a lot of duplicate records.
For example, for ArrayLength = 12 I generate 24720 records, but only 792 records are valid.
I have to compare the rest with each other and delete them - this is not efficient :(

Thank you for your advice...
Title: Re: Algoritm for combination of numbers
Post by: Jorg3000 on December 22, 2024, 08:48:40 pm
Hi!
Are the values in Myarray unique or can the array (up to ArrayLength) contain duplicates?
Title: Re: Algoritm for combination of numbers
Post by: Roman on December 22, 2024, 08:53:51 pm
He said: "number must not repeat".
Title: Re: Algoritm for combination of numbers
Post by: Warfley on December 22, 2024, 09:12:44 pm
Have you tried this: https://stackoverflow.com/questions/8316479/combination-without-repetition-of-n-elements-without-use-for-to-do#8332722
Title: Re: Algoritm for combination of numbers
Post by: Jorg3000 on December 23, 2024, 06:08:33 am
Hi!
You can speed up the generation considerably by directly generating only valid results.
To do this, you do not work directly with the values, but with indexes (indices) that represent a value.
The indices are incremented in the same way as the digits of a number.

To make the procedure a little leaner, I have taken the liberty of replacing the players n1 ... n7 with an array. This also has the advantage that you can change the number of players later.

Code: Pascal  [Select][+][-]
  1. const NumberOfPlayers = 7;
  2.  
  3. type DataResult = record
  4.   Players: array[0..NumberOfPlayers-1] of Byte;  // instead of n1 .. n7
  5. end;
  6.  
  7. procedure GenerateCombinations();
  8. var
  9.   Indices: array[0..NumberOfPlayers-1] of Byte;
  10.   i, k, pos: Integer;
  11. begin
  12.   if NumberOfPlayers > ArrayLength then begin WriteLn('Error: NumberOfPlayers must not be greater than ArrayLength.'); Exit; end;
  13.  
  14.   ResultCount:=0;
  15.   for i:=0 to NumberOfPlayers-1 do    Indices[i] := i+1;
  16.  
  17.   while True do
  18.   begin
  19.     for k := 0 to NumberOfPlayers - 1 do
  20.       ResultArray[ResultCount].Players[k] := Myarray[Indices[k]];
  21.  
  22.     inc(ResultCount);
  23.  
  24.     pos := NumberOfPlayers-1;
  25.     while (pos >= 0) and (Indices[pos] = ArrayLength - NumberOfPlayers + pos + 1) do  dec(pos);
  26.  
  27.     if pos<0 then Exit;
  28.     inc(Indices[pos]);
  29.     for i := pos+1 to NumberOfPlayers-1 do    Indices[i] := Indices[i-1] + 1;
  30.   end;
  31. end;
  32.  
Title: Re: Algoritm for combination of numbers
Post by: embedded-systems on December 23, 2024, 10:02:22 pm
To Jorg3000:

Thanks a lot - this algorithm is perfect.
It works as it should and it's fast. Great inspiration for me !!!

Have a wonderful Christmas holidays and thanks again for your help. Lukas
Title: Re: Algoritm for combination of numbers
Post by: Jorg3000 on December 24, 2024, 06:35:21 am
I'm very glad that it works.
I'm considering whether I should turn it into a universal function.

Merry Christmas to everyone!
Jörg

TinyPortal © 2005-2018