Algorithm to find all possible combinations given the length of the number and what numbers are available

[John Davis]

For example:

Let us say we can use any number from 0-4 and we have numbers that can be 4 digits long then there would be 5^4 = 625 possible numbers that you can have. 0000, 0001 ... 4444.

Now lets say the numbers available are from 0-9 and the length of the number can be 1-n for a general case.

I am struggling to understand the way I can go about this for a general case. If given the parameters you can do this easily with nested for loops.

I was thinking of using a vector of a vector to do this however I just cant get my head around it. Any ideas?

[lastchance]

If you have a FIXED length of number, say r, then the number of possibilities is
10^r.

If you can have ANY length of number between 1 and n, then the number of possibilities is the sum for individual lengths:
10¹+10²+10³+...+10ⁿ
This is just a geometric series (first term 10, common ratio 10, n terms) with sum
10*(10ⁿ-1)/9

Either way ... it's a one-liner (unless you actually intend to list those numbers).

[John Davis]

I am trying to generate them all and then put them into a list.

so for each set of numbers the length would be constant and hence as you said is howManyNumbersAllowed^length.


I am not sure what you mean here by a geometric series, I don't think this applies here apologies If I worded this incorrectly.

[lastchance]

I was assuming you wanted to count them, rather than list them. However.

To get all 10 numbers of length 1, push_back those digits into a vector.

To get all 100 numbers of length 2, then for each member of the previous vector, push_back into a new vector all 10 numbers formed by adding a different digit to their end.

Continue recursively.
To get all numbers of length n, if you have so far got all numbers of length n-1 then, for each of those numbers, store (i.e. push_back into a fresh vector) that number appended by each digit 0...9.


But if the digits are just 0...9 then you could just count them into the vector with a loop! Or use std::iota.

[Duthomhas]

First, a quick clarification so we can all use the same vocabulary:

    NDIGITS = total length of your number in digits (your example: 4-digits long)
    RADIX = total number of values per power (your example: radix = 5 for digits [0,1,2,3,4])

Look at the polynomial lastchance showed you: it is a geometric series. Replace 10 with the RADIX you intend to use.


To generate a list of them, you simply need to start with zero and start counting. Stop when you have reached RADIX*(RADIX**NDIGITS-1)/(RADIX-1).
[edit]
er, I don’t know what stupid I was thinking. The number of numbers is:
  radix * radix**(ndigits - 1) - 1

To print each number, you will need to decompose the number div-mod your RADIX. This is true if you need to convert to string or to a decimal value.

Alternately, you can maintain a list of digit values and perform an addition with carry on them, just like a bignum class. Complicating your add makes printing a little simpler. And also you only need make your digit vector NDIGITS elements long, and simply stop when the last digit wraps back to zero.

I would personally do it the second way, but either way you are going to cost a lot of time to compute this, purely for the modular arithmetic.

Hope this helps.

[edit]
I wrote a little program to play:

program p;
{$apptype console}
uses
  Math, SysUtils;

function radix_to_decimal( value, radix: cardinal ): cardinal;
  begin
  if value < radix 
    then result := value
    else result := (value mod radix) + (radix_to_decimal( value div radix, radix ) * 10)
  end;

var
  radix, ndigits, value, max_value: cardinal;

begin
Write( 'radix? '   );  Readln( radix   );
Write( 'ndigits? ' );  Readln( ndigits );

max_value := radix * Trunc( Power( radix, ndigits - 1 ) ) - 1 ;

for value := 0 to max_value do
  Writeln( Format( '%.*d', [ndigits, radix_to_decimal( value, radix )] ) )
end.

Heh heh heh...

[John Davis]

That does make sense now thanks.

On the question of time and efficiency.

The reason I am doing this is because I am trying to create a solver for the mastermind game using knuths Algorithm: [http://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf]

In 1977, Donald Knuth demonstrated that the codebreaker can solve the pattern in five moves or fewer, using an algorithm that progressively reduced the number of possible patterns.[11] The algorithm works as follows:

1) Create the set S of 1296 possible codes (1111, 1112 ... 6665, 6666)

2) Start with initial guess 1122 (Knuth gives examples showing that other first guesses such as 1123, 1234 do not win in five tries on every code)

3) Play the guess to get a response of colored and white pegs.

4) If the response is four colored pegs, the game is won, the algorithm terminates.

5) Otherwise, remove from S any code that would not give the same response if it (the guess) were the code.

6) Apply minimax technique to find a next guess as follows: For each possible guess, that is, any unused code of the 1296 not just those in S, calculate how many possibilities in S would be eliminated for each possible colored/white peg score. The score of a guess is the minimum number of possibilities it might eliminate from S. A single pass through S for each unused code of the 1296 will provide a hit count for each colored/white peg score found; the colored/white peg score with the highest hit count will eliminate the fewest possibilities; calculate the score of a guess by using "minimum eliminated" = "count of elements in S" - (minus) "highest hit count". From the set of guesses with the maximum score, select one as the next guess, choosing a member of S whenever possible. (Knuth follows the convention of choosing the guess with the least numeric value e.g. 2345 is lower than 3456. Knuth also gives an example showing that in some cases no member of S will be among the highest scoring guesses and thus the guess cannot win on the next turn, yet will be necessary to assure a win in five.)

7)Repeat from step 3.


The issue with this algorithm is that this method works maybe up around 9 by 9 but when you get to big numbers it takes way too long to store all the numbers.


I am trying to find some other way to allow this to get to bigger numbers lets say up to 15-20.
I don't think that this is even theoretically possible?

[Duthomhas]

Don’t store all the numbers. Pull them by index.

I have never messed with this algorithm (nor played Mastermind), but I suspect that it is more efficiently possible to track patterns of numbers not in the set than to keep an entire set of numbers...

[John Davis]

What do you mean by pull them by index? If you don't have a set of the solutions, where exactly would you be pulling the indexes from?

[John Davis]

@last chance I tried implementing the recursive function you mentioned but there are too many moving parts and Its is getting confusing. To do this you would need to know 4 things:

the length of the code
Up to what number it can be
the position of the digit in the code


How would I even go about doing a recursive function for this?

[lastchance]

Actually, I've come round to the view that it's simpler just to count!

If you have numbers 0...9 and, say, length 4, then simply count 0000, 0001, 0002, ...., 9999

If you have numbers 0...5 say, then count 0000, 0001, 0002, ...., 5555 in base 6.

If you have numbers 1....6 then map them to 0....5 and do the above.

If you have characters ABCDEF then map them to 0....5 and do the above.

So, I was wrong about recursion - I would just count.

[Duthomhas]

Yes, counting.

What I meant by “index” was that you are dealing with counting numbers —just in a different base (radix) than we are used to using.

So if you have, say, 1122, you can consider it an actual number, just in base 5 (the radix, or number of digit glyphs available, is 5).

You can easily convert from radix=5 to radix=10 and back again, and you can easily perform additions or other manipulations on the number by simply being aware of the radix you are starting with.

So, if you want to add or modify a number based on any algebraic property, say, add 2200₅ to it, you really only need to convert the addend to radix=10 and add it in.

Hope this helps.

[John Davis]

@lastchance, Counting would not work for this right?

say we had a 4 letter number and could only have the numbers 0, 1 and 2

you would need to be able to limit the digits to not be any higher than 2 so It would not be possible to count them you would infact have to use a recursive loop but how Is the confusing part.

[John Davis]

void createSet() {

    vector<int> current(CODE_LENGTH, 0);
    vector<int> elements;

    for (int i = 1; i <= NUM_COLOURS; ++i) {
        elements.push_back(i);
    }

    combinationRecursive(CODE_LENGTH, 0, current, elements);
}

void combinationRecursive(int combinationLength, int position, vector<int> &current, vector<int> &elements) {

    if (position >= combinationLength) {
        combinations.push_back(current);
        return;
    }

    for (int j = 0; j < elements.size(); ++j) {
        current[position] = elements[j];
        combinationRecursive(combinationLength, position + 1, current, elements);
    }
    return;
}

I found this as an example online but I dont really understand what its doing.

[lastchance]

John Davis wrote:

@lastchance, Counting would not work for this right?

say we had a 4 letter number and could only have the numbers 0, 1 and 2

you would need to be able to limit the digits to not be any higher than 2 so It would not be possible to count them

You count from 0 to 80 and convert to base 3 when required.

   Base 10     Base 3
         0      0000
         1      0001
         2      0002
         3      0010
         4      0011
         5      0012
         6      0020
         7      0021
         8      0022
         9      0100
        10      0101
        11      0102
        12      0110
        13      0111
        14      0112
        15      0120
        16      0121
        17      0122
        18      0200
        19      0201
        20      0202
        21      0210
        22      0211
        23      0212
        24      0220
        25      0221
        26      0222
        27      1000
        28      1001
        29      1002
        30      1010
        31      1011
        32      1012
        33      1020
        34      1021
        35      1022
        36      1100
        37      1101
        38      1102
        39      1110
        40      1111
        41      1112
        42      1120
        43      1121
        44      1122
        45      1200
        46      1201
        47      1202
        48      1210
        49      1211
        50      1212
        51      1220
        52      1221
        53      1222
        54      2000
        55      2001
        56      2002
        57      2010
        58      2011
        59      2012
        60      2020
        61      2021
        62      2022
        63      2100
        64      2101
        65      2102
        66      2110
        67      2111
        68      2112
        69      2120
        70      2121
        71      2122
        72      2200
        73      2201
        74      2202
        75      2210
        76      2211
        77      2212
        78      2220
        79      2221
        80      2222

#include <iostream>
#include <iomanip>
#include <string>
using namespace std;

const string digits = "0123456789ABCDEF";


string toBase( int n, int base, int length )
{
   string result;
   for ( int i = 0; i < length; i++ )
   {
      result = digits[ n % base ] + result;
      n /= base;
   }
   return result;
}


int main()
{
   const int base = 3;
   const int length = 4;

   int mx = 1;
   for ( int p = 0; p < length; p++ ) mx *= base;
   mx--;

   #define SW << setw( 10 ) <<
   cout SW "Base 10" SW "Base " << base << '\n';
   for ( int n = 0; n <= mx; n++ )
   {
      cout SW n SW toBase( n, base, length )<< '\n';
   }
}

[John Davis]

This is making more sense now Thank you.

One thing I am confused about it, what does this do and how does it work:

const string digits = "0123456789ABCDEF";

In addition why is result declared as a string, Would not just double?

[lastchance]

One thing I am confused about it, what does this do and how does it work:

const string digits = "0123456789ABCDEF";

It is just a container for the mapped possible output characters. For here it was originally used for number base conversions up to hexadecimal.

If you had wanted to use possible outputs of 1,2,3 instead of 0,1,2 that mapping could be achieved by
const string digits = "123";

If you had wanted to use possible outputs of R, G, B that mapping could be achieved by
const string digits = "RGB";