Challanging algorithm for all possible combinations

[pholotic]

A few days ago I got a "bright idea" to see if I could match a string, with an arbitrary length from 1 to 12, to its formulated sequence by using an algorithm to find all possible combinations of the integer combinations from 0 to 9 at each length (1 to 12).

Example: Desired numerical combinations from integers 1 to 3:

At Length 1:

1, 2, 3

At Length 2:

11, 12, 13, 21, 22, 23, 31, 32, 33

At Length 3:

111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333

And so on until the nth length (in my case a length of 12).


First off, I would like to say that this is not as easy as I thought. I clearly underestimated the problem seeing as I've spent hours attempting to write a working algorithm, but feel like I've made no progress.

Here are a few of my attempts:

Attempt 1:

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>

using namespace std;

const int MAX = 12; //Max input length
string input, guess;

int power(int q, int n)
{
	int _q = q;
	if(n == 0)
		return 1;
	for(int i = 1; i < n; ++i)
		q *= _q;
	return q;
}
int main() {
        int s = 0;
	int temp = 0;
	for(int i = 0; i < 3; ++i) {
		guess.append(1u,' ');
		for(int j = 0; j < power(3,i); ++j) {
			for(int k = 49; k <= 51; ++k) {
				if((j%2) == 0)
					s = 0;
				if(i > 0)
					for(int n = 0; n < i; ++n)
						guess[i-n] = s + 49;
				guess[i] = k;
				cout << guess << endl; }
			//temp = s;
			//guess[0] = s + 49;
			s++; }}
        system("pause");
	return 0;
}

This failed after all of my attempts. I managed to get only a few desired outputs.

Attempt 2:

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>

using namespace std;

const int MAX = 12; //Max input length
string input, guess;

int main() {
        const int amt = 3;
	const int kamt = 5;
	char keyValue[kamt] = {49,50,51,52,53}; // 1,2,3,4,5
	char permute[amt];

	for(int i = 0; i < 4; ++i) {
		guess.append(1u,' ');
		if(i == 0) {
			for(int j = 0; j < kamt; ++j) {
				guess[i] = keyValue[j];
				cout << guess[i] << endl; }}
		else 
			for(int j = 0; j < amt; ++j)
				for(int k = 0; k < amt; ++k) {
					permute[k] = keyValue[k+j];
					sort(permute,permute+amt);
					while(next_permutation(permute,permute+(i+1))) {
						for(int m = 0; m < i; ++m)
							cout << permute[m]; 
						cout << endl; }}}

        system("pause");
	return 0;
}

I can't exactly explain this one. It works if the length is 2 or less; however, the order of the output is horrendous.

Attempt 3:
I tried using recursion, but only found myself getting more and more lost the further I tried developing my function. Cannot find my work for this attempt.



I would really like to figure this out on my own, but I am very stuck as you can see. I also lack time that I can spend working on this since im a full time student.

I welcome all advice, suggestions, comments, hints, etc.

Thank you in advance for taking a glance at this. I apologize for the length of the post.

[Disch]

You are over complicating this. This can be done very simply with one... maybe 2 loops.

Think about how you do it in your mind:

1) all digits start at their lowest value
2) increment right-most digit.
3) if there are no more digits, reset rightmost digit and increment the one to the left of it
4) repeat from step 2


It's really that simple. We're talking maybe 6-10 lines of code for the permutation loop(s).

[pholotic]

Thanks for the timely response.

Would this be the case for character types with a range from 32 to 126?

What if I entered a string were each section could be any ASCII value from that range, and had an alorithm to run through each character combinations for all of the lengths until a "guess" string is matched with the input string?

[Disch]

Regardless of how many elements there are and/or the range of those elements -- the logic remains the same. The only thing that would change is a few variables.

[D80DSL3A]

I couldn't get it quite that simple. I used recursion to cycle through the digit values and an array passed as an argument for keeping track of the current values. It does produce the desired output, but it's 13 lines of code.

@pholotic. Would you like to see it? I ask so as not to spoil your challenge by posting it.

[pholotic]

I have been thinking about what all has been said quite a bit. I will make another attempt later today and post my results. I think after this next attempt I would rather just see an example so I can move along with my life. hahaha.

[IndieExe]

I recently wrote a program that can generate all possible combinations of a character set that can exist within a set of character positions. For example all combinations 5 positions can have when each 1 position can have a value from a to z;

The algorithm for this process is the same algorithm that we use for numbers.

01,
02,
03,
04,
05,
06,
07,
08,
09,
10,
11.....

Starting at the most right position, you increment it until it reaches it's end.
Then you reset it, and increment the next last position by one until that position reaches it's end.

Whenever you reaches the end of a position(it's max range(say z)), you check if the preceeding position is at it's end, if it is then you check the preeceding preceeding, and so on until you reach the left most position, and that it is not the last value. If the preeceding is not at it's end, then you reset the following positions, and begin the process all over again.


Btw, if it helps you, i came to the conclusion that the max number of combinations in a given set of positions and a given range is (rng2-rng1+1)^positions.

[eklavya sharma 2]

It is like base conversion:
Solution for first example in this thread is like counting in base 3 (add one to each digit to get answer)

0
1
2

00
01
02
10
11
12
20
21
22

000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122
200
201
202
210
211
212
220
221
222

[pholotic]

Thank you for the replies. I attempted solving this again last night and ended up coming up with something similar to what I have already wrote, which does not work. All help is very appreciated. Thanks.

[Disch]

pholotic wrote:

I think after this next attempt I would rather just see an example so I can move along with my life.

pholotic wrote:

I attempted solving this again last night and ended up coming up with something similar to what I have already wrote, which does not work. All help is very appreciated. Thanks.

So it sounds to me like you're okay with seeing code now.

I imagined something like this:

For all permutations:
000
001
010
011
100
101
110
111


Untested:

int num_digits = /*number of digits .. ie 3*/;
char lowval = /* the low ASCII value... ie... '0' */
char highval = /* the high ASCII value... ie... '1' */

std::string digits;
for(int i = 0; i < num_digits; ++i)  // there's probably a better way to init this
    digits += lowval;   // but I'm too lazy to look it up

bool running = true;
while( running )
{
    std::cout << digits << std::endl;

    int i;
    for( i = num_digits-1; i >= 0; --i )  // go through all digits
    {
        if( digits[i] == highval )  // has this digit gone through all permutations?
            digits[i] = lowval;  // if yes, reset it to the low val.  When the for() loop iterates
                     // it will update the next digit
        else  // if not...
        {
            ++digits[i];  // increment it 
            break;   // and stop going through all digits
        }
    }

    if( i < 0 )  // if all digits have completed all permutations
        running = false;  // we're done
}

[greenleaf800073]

The best I came up with this, I hope you can manipulate though...

Can't think right now...

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

void generator(int number,int perm)
{
    for(int i = 0;i < number;i++)
    {
        cout << perm;
    }
    cout << endl;
}

int main(int nNumberofArgs,char* pszArgs[])
{
    int number;
    cout << "Enter number: ";
    cin >> number;

    for(int i = 1;i < number + 1;i++)
    {
        generator(number,i);
    }
    return 0;
}

[pholotic]

Greenleaf, I really appriciate the help. Unfortunately, there's not a whole I can do with your code since I'm already at that point in my issue. Thank you very much for trying, however.

Disch, the code you provided works good. It does the main part that I was struggling with. Thank you.

I don't understand why I could not figure this out. It seemed relatively simple, but I struggled with it when I actually got started. I seem to overcomplicate some of my code quite often. Not sure why this is for such easy problems.

[D80DSL3A]

Here's what I came up with. The sequence of values starts at beginVal. For the example below beginVal=1 and sz=4 so all combinations of 1 2 3 4 will be shown. An array of sz unsigned ints are needed for the function, which is passed from main.

#include <iostream>
using std::cout;
using std::endl;

// gives all combinations when values are sequential.
void enum_combs2( unsigned beginVal, unsigned x[], unsigned sz, unsigned subSz, unsigned place = 0 )
{
    if( place == subSz )
    {
        for(unsigned i=0; i<subSz; ++i) cout << x[i] + beginVal;
        cout << ", ";
        return;
    }

    for( unsigned i=0; i<sz; ++i )
    {
        x[place] = i;
        enum_combs2(beginVal, x, sz, subSz, place+1 );
    }
    return;
}


int main(void)
{
    unsigned idx[4] = {0};// array needed by enum_combs2()

    enum_combs2(1, idx, 4, 1);// sets of 1 element
    cout << endl << endl;
    enum_combs2(1, idx, 4, 2);// sets of 2 elements
    cout << endl << endl;
    enum_combs2(1, idx, 4, 3);// sets of 3 elements
    cout << endl << endl;
    enum_combs2(1, idx, 4, 4);// sets of 4 elements

    cout << endl;
    return 0;
}

1, 2, 3, 4,

11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44,

111, 112, 113, 114, 121, 122, 123, 124, 131, 132, 133, 134, 141, 142, 143, 144,
211, 212, 213, 214, 221, 222, 223, 224, 231, 232, 233, 234, 241, 242, 243, 244,
311, 312, 313, 314, 321, 322, 323, 324, 331, 332, 333, 334, 341, 342, 343, 344,
411, 412, 413, 414, 421, 422, 423, 424, 431, 432, 433, 434, 441, 442, 443, 444,


1111, 1112, 1113, 1114, 1121, 1122, 1123, 1124, 1131, 1132, 1133, 1134, 1141, 11
42, 1143, 1144, 1211, 1212, 1213, 1214, 1221, 1222, 1223, 1224, 1231, 1232, 1233
, 1234, 1241, 1242, 1243, 1244, 1311, 1312, 1313, 1314, 1321, 1322, 1323, 1324,
1331, 1332, 1333, 1334, 1341, 1342, 1343, 1344, 1411, 1412, 1413, 1414, 1421, 14
22, 1423, 1424, 1431, 1432, 1433, 1434, 1441, 1442, 1443, 1444, 2111, 2112, 2113
, 2114, 2121, 2122, 2123, 2124, 2131, 2132, 2133, 2134, 2141, 2142, 2143, 2144,
2211, 2212, 2213, 2214, 2221, 2222, 2223, 2224, 2231, 2232, 2233, 2234, 2241, 22
42, 2243, 2244, 2311, 2312, 2313, 2314, 2321, 2322, 2323, 2324, 2331, 2332, 2333
, 2334, 2341, 2342, 2343, 2344, 2411, 2412, 2413, 2414, 2421, 2422, 2423, 2424,
2431, 2432, 2433, 2434, 2441, 2442, 2443, 2444, 3111, 3112, 3113, 3114, 3121, 31
22, 3123, 3124, 3131, 3132, 3133, 3134, 3141, 3142, 3143, 3144, 3211, 3212, 3213
, 3214, 3221, 3222, 3223, 3224, 3231, 3232, 3233, 3234, 3241, 3242, 3243, 3244,
3311, 3312, 3313, 3314, 3321, 3322, 3323, 3324, 3331, 3332, 3333, 3334, 3341, 33
42, 3343, 3344, 3411, 3412, 3413, 3414, 3421, 3422, 3423, 3424, 3431, 3432, 3433
, 3434, 3441, 3442, 3443, 3444, 4111, 4112, 4113, 4114, 4121, 4122, 4123, 4124,
4131, 4132, 4133, 4134, 4141, 4142, 4143, 4144, 4211, 4212, 4213, 4214, 4221, 42
22, 4223, 4224, 4231, 4232, 4233, 4234, 4241, 4242, 4243, 4244, 4311, 4312, 4313
, 4314, 4321, 4322, 4323, 4324, 4331, 4332, 4333, 4334, 4341, 4342, 4343, 4344,
4411, 4412, 4413, 4414, 4421, 4422, 4423, 4424, 4431, 4432, 4433, 4434, 4441, 44
42, 4443, 4444,

[Smac89]

Here is one I did a long time ago.

#include <iostream>
#include <cstring>
#include <cstdio>

void _swap (char&, char& );
long Fact(int num);
void _permute(char* , int);
void _Print(char*);
void _sort(char *, int );

int main()
{
  char A[100];
  printf("Enter the string/set of numbers: ");
  gets(A);
  
  int k;
  
  k = strlen(A);
  
  _permute(A, k);  
  
  return 0;
}


void _swap(char &X, char &Y)
{
  char Z;
  Z = X;
  X = Y;
  Y = Z;
}


void _sort(char *myStr, int size)
{
  bool didSwap;
  
  do
  {
    didSwap = false;
    
    for (int y = 1; y < size; ++y)
      if (myStr[y] < myStr[y-1])
      {
	_swap(myStr[y], myStr[y-1]);
	didSwap = true;
      }
      
  } while (didSwap);
}

void _permute(char *myStr, int size)
{  
  bool can_permute = true;
  long Start = Fact(size);
  
  _sort(myStr, size);
  
  _Print(myStr);
  
  int large = size - 1;
  
  while(--Start > 0)
  {
    if (can_permute)
    {
      _swap(myStr[large], myStr[large - 1]);
      _Print(myStr);
      large--;
    }
    else
    {
      _swap(myStr[large], myStr[large + 1]);
      _Print(myStr);
      large++;
    }
    
    
    if (large == 0 || large == (size - 1))
      if (--Start > 0)
      {
	if (large == 0)
	  _swap(myStr[size - 1 - large], myStr[size - 2 - large]);
	else
	  _swap(myStr[size - 1 - large], myStr[size - large]);
	
	_Print(myStr);
	can_permute = (large == 0 ? 0 : 1);
      }
  }
  
}

void _Print(char *Arr)
{
  while (*(Arr))
    std::cout << *Arr++ << " ";
  std::cout << std::endl;
}

long Fact(int num)
{
  if (num == 1)
    return 1;
  return (num * Fact(num-1));
}

It uses the Steinhaus–Johnson–Trotter algorithm aka minimal changes algorithm to give a not so lexicographic permuation of a range of values. Still can't wrap my head around the lexicographical aspects. What makes this one unique is that not only does it only change 2 values per iteration, but the only operation it does on those 2 values is to swap them.

[cire]

A more novel implementation. Note that sequences are not generated in lexographical order.

#include <algorithm>
#include <vector>
#include <iostream>

class sequence
{
public:
    sequence(char begin, char end, unsigned length) ;
    char const* c_str() const { return _v.data() ; }

    unsigned length() const { return _v.size()-1; }
    operator bool() const ;

    sequence& operator()() ;
private:
    char _beg, _end ;
    std::vector<char> _v ;
};

sequence::sequence( char begin, char end, unsigned length )
    : _beg(begin), _end(end), _v(length+1)
{
    std::fill(_v.begin(), _v.end()-1, _beg) ;
}

sequence::operator bool() const
{
    return _v.back() == 0 ;
}

sequence & sequence::operator()()
{                                            // anyone for a little pointer shenanigans?
    char* c = _v.data() ;

    while ( ++(*c) > _end )
        *c++ = _beg ;

    return *this ;
}

std::ostream & operator<<(std::ostream& os, const sequence& seq)
{
    return os << seq.c_str() ;
}

int main()
{
    sequence seq('1', '3', 3) ;

    do
    {
        std::cout << seq << '\n' ;
    } while ( seq() ) ;
}

[Edit: I have to admit the purpose of the original post makes me wonder if this is necessary. Wouldn't it be easier to just check the string in question to see if it was made up of the appropriate characters, rather than generating all unique permutations of all combinations? Perhaps I'm misunderstanding what you're trying to accomplish.]