Generating and sorting permutations

[claytonl]

Hey, I'm not a programmer at all, but I'm hoping someone could help me
solve a problem. I've looked all over Google, Ruby forums, and C/C++
forums but havn't found my answer. I'm trying to generate all possible
permutations for 5 digits (1,2,3,4,5), up to and including 6 digits
long, in order from smallest to largest, broken into sets of numbers
with different lengths, including number repeats within the same number
(1112 for example), then filter out any numbers that don't include 1
anywhere. Wow thats a mouthful. Heres an example of what I mean.

1 digit long

1

2 digits long

11
12
13
14
15
21
31
41
51

and so on to 6 digits. Any help would be greatly appreciated! Thanks!

[nexocentric]

The solution to your problem isn't that difficult... well not for someone with some programming experience.

If you are looking to program a solution to this problem the steps that I would take would be the following.

1. Generate a list of numbers from 1 - 999999 because you want a max of 6 digits long

2. Scan through and make a second list numbers that only contain the numbers that you listed

3. Scan through the list that you just generated and group each by number of digits

I don't know what you're thinking about doing for the actual programming, but a simple C/C++ program could do that pretty quick.

[claytonl]

Unfortunately, I don't program. I've always wanted to learn how. I was hoping someone could write a simple program, it would be much appreciated! I completely understand that you have better things to do than write programs for random people though. Even if you could give me the name of some commands I could use, I could read a book about those specific things. I started typing out all of the numbers but quickly realized that its ridiculous to. As far as I can tell, its 14070 numbers that fit the description. Thank you very much for the reply, if you could steer me in any direction towards commands or anything of the sort, I would be very greatful. Thanks!

[nexocentric]

What would you think of me writing a list of functions that I would use and then a little bit more detailed flow, and you research how to use the functions and put them together? I'll give you some pointers if you have any other questions? So I won't be doing it for you I'll just be stepping you through it.

[claytonl]

That would be awesome!

[nexocentric]

I'm going to assume that you're using Windows, in which case I would suggest downloading Visual C++ Express Edition. The Latest one will be fine. There are lots of other ways to begin C/C++ programming, but if you download and install that, which is free BTW, then you won't have to worry about setting up enviroment variables or other things.

If you could go ahead and download that and do the, console application tutorial included with it you should be ready for the stuff I'll give you.

[claytonl]

I'm actually using Linux (Ubuntu to be more specific). I have a couple IDEs and some compilers, but any advice for which I should use would be great. For previous experiments I've just edited in nano and compiled in the terminal. Do you have any recommendations?

[nexocentric]

If you can use nano then it should be no problem getting started doing it in Linux and if you know how to compile already then you should be good to go! :) terminal will be good enough for what you're doing.

Could you give me a bit to get things in order? I'm at work right now... :(

[claytonl]

Hey no problem! I'm in no big rush.

[nexocentric]

claytonl,

I went ahead and made the program that you asked so that I could see what functions I used.

Functions used:
memset
atoi
sprintf
strstr
new ( this starts dealing with pointers so we'll go ahead and start small and not use it at first )

I also wrote the whole program using only the variable types char, int, and bool.

In total the program I wrote used 5 for loops. It could probably be done with less, but that's okay.

Loop 1 filled an array with all the single digits from 0 - 9
Loop 2 marked which digits were to be used in finding permutations
Loop 3 generated all numbers from 0 - 10^n - 1 (n = number of digits)
Loop 4 and loop 5 checked to see if a number generated in loop 3 was indeed a permutation that we asked for
Loop 6 excluded permutations that did not have the specified required digit ( in our case 1)

This isn't the only or best way to do this. I just what I did. I guess what you could do now is start with using loops to fill arrays? Also when it comes to looking up what functions do what www.cplusplus.com is a great resource. Just type the function name in the search and it should bring up a page of what it does and lots of times an example of how to use it. If you have any questions please feel free to ask.

[ArkM]

The only special function you needed is main. It's C++, why memset, atoi and other C stuff?

[nexocentric]

The only special function you needed is main. It's C++, why memset, atoi and other C stuff?

You could just use main! My mistake. I think I made it so you could do any number of permutations and any number of digits by reflex. Should I write what I used the functions for for reference?

[claytonl]

Alright I'm in way over my head, but I have an idea. Could this be done in 3 steps? I couldn't figure out how to use arrays, but I was able to generate numbers in a file. Keep in mind I've never wrote anything in C++ before.

1. Fill a file with digits from 1-51. 51 would be the last number that fits my criteria that is 2 digits long. I assume I could just make that number 555555 for the final result (I want up to 6 digits).

#include <fstream>
using namespace std;

int main ()
{
// make txt file, fill with numbers
ofstream myfile;
myfile.open ("numbers.txt");
int a=1;
while (a<52)
{
myfile << a << "\n";
a++;
}
myfile.close();
return 0;
}

2. Remove numbers that contain 0,6,7,8, or 9

3. Remove numbers that don't contain 1.

I'm not sure how to do the other two steps. I havn't been successful even reading a file. I've looked at a couple tutorials on using loops to generate arrays and on file editing. I'll see what the main function is all about, and I'll keep looking at more tutorials, but any help would be appreciated!

[nexocentric]

Working with a file is fine, but you could do everything in the program. It'd be easier than writing to and reading from a file.

This is a possible step one.
1) make an array big enough to hold all numbers in the range 0 - max number of digits
2) use a loop to fill that array will all all numbers in that range

After that we can go on to step 2

[claytonl]

I keep getting a segmentation fault when I try to execute the program. I can't see why. I put the cout at the end just to make sure I'm doing things properly, but I'm not.

#include <iostream>
using namespace std;

int main ()

{
int a;
int numbers [52];
while (a<52)
{
numbers[a] = a;
a+1;
}
cout << numbers << endl;
return 0;
}

[nexocentric]

I keep getting a segmentation fault when I try to execute the program. I can't see why. I put the cout at the end just to make sure I'm doing things properly, but I'm not.

#include <iostream>
using namespace std;

int main ()

{
int a;
int numbers [52];
  while (a<52)
    {
    numbers[a] = a;
    a+1;
    }
cout << numbers << endl;
return 0;
}

When you want to add one to a number you can do it by
a++;
or
a = a + 1;

Also when you want to output a variable from an array you have to tell the computer which one you want to output.
You stored something in numbers[a], so when you output you also have to output using numbers[a] or numbers[0], numbers[1], ect.

Go ahead and try that and see if you still get the segfault.

Also when you post code, if you highlight it and click the code button before you post it makes it easier to read.

[claytonl]

I've discovered the code button after posting this and editing several times. I was using quick reply, and I just put code tags around the text. Still no colors though.

#include <iostream>
using namespace std;

int main ()

{
int a=0;
int numbers [52];
  while (a<52)
    {
    numbers[a] = a;
    a++;
    }
cout << numbers[23] << numbers[44] << endl;
return 0;
}

Ok! It shows me the numbers 23 and 44! So it appears I'm storing numbers in the array. How do I filter out the numbers I don't want?

[nexocentric]

Okay, before we filter out the numbers we don't want we need to make a list of all possible digits, so let's make another array of the digits 0 - 9. It might be easier to make it a char array. This is so we can check what numbers contain the digits that we specify.

[claytonl]

I'm not entirely sure what you're asking me to do, but I think this might be it. I've added in what I believe to be a char array containing digits 0-9.

#include <iostream>
using namespace std;

int main ()

{
int a=0;
int first [52];
char digits [] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  while (a<52)
    {
    first[a] = a;
    a++;
    }
return 0;
}

[jencas]

http://www.sgi.com/tech/stl/next_permutation.html

[claytonl]

I tried compiling the code in the page with no luck. I'm actually pretty sure you arn't supposed to be able to. The command sounds useful but I'm not sure how to use it. Even if I could just come up with all the permutations of 1,2,3,4,5 for up to 6 digits (including repeats like 111345) in order from smallest to largest, I could just remove the ones with no 1 in them in a text editor. That sounds like it should be easy enough, but of course I don't know what I'm doing.

[nexocentric]

As suggested I'm posting the code that I wrote for you to look at. I included an explanation of what I did. There are probably going to be quite a few things that you don't understand, but that's okay. You can start by working with what you do understand and then asking questions or researching from there. :)

#include <iostream>

int CountPermutations_func( int i_numberOfDigits, int * i_withNumbers_ary_ptr, int i_numberArraySize, char * c_requiredNumber_ptr )
{

	bool b_match; // flags us in case of a match true = match false = nomatch
	char * c_charCheck_ptr; // used to find banned digits
	char * c_maxNumbers_ary_ptr; // this holds the maximum number of digits
	char c_digitAsString_ary[2]; // holds a digit as a string for check purposes
	char c_digits_ary[11]; // holds all digits from 0 - 9
	int * i_matchList_ary_ptr; // this is a list of our matches
	int * i_numberList_ary_ptr; // this is a list of numbers from 0 to the number we specified
	int i_checkPermutations; // this is used for runnning the loop to check permutations
	int i_fillArrayLoop; // this is used for running the loop to fill i_numberList_ary_ptr
	int i_matchCount; // this is the number of current matches
	int i_numberLimit; // this is used to store, in this case, the number 999999

	/* declarations */
	i_matchCount = 0;
	/***********************************************************/
	/* in this i tend to use the function memset a lot. you    */
	/* bascially use it to make sure that a string has been    */
	/* initialized properly.  you don't have to use it, but it */
	/* makes debugging easier if you do                        */
	/***********************************************************/
	// allocate memory for max number of digits
	c_maxNumbers_ary_ptr = new char[i_numberOfDigits + 1];
	// initialize c_digitAsString_ary
	memset( c_digitAsString_ary, 0x00, sizeof(c_digitAsString_ary) );
	// initialize c_maxNumbers_ary_ptr
	memset( c_maxNumbers_ary_ptr, 0x00, i_numberOfDigits + 1 );
	// set c_maxNumbers_ary_ptr = to  10^i_numberOfDigits - 1
	memset( c_maxNumbers_ary_ptr, 0x39, i_numberOfDigits);
	// initilize digits array
	memset( c_digits_ary, 0x00, sizeof(c_digits_ary) );

	// the biggest number to be included in search for permutations as an integer
	i_numberLimit = atoi(c_maxNumbers_ary_ptr);
	
	// create an array for matches as big as the maximum possible number of intergers in this run
	// we don't need an array that big, but allocating memory onces saves us problems later
	i_matchList_ary_ptr = new int[i_numberLimit];
	// create an array for all numbers from 0 to 10^i_numberOfDigits - 1
	i_numberList_ary_ptr = new int[i_numberLimit];

	/* get all possible digits 0 - 9 */
	for ( i_fillArrayLoop = 0; i_fillArrayLoop < sizeof(c_digits_ary) -1 ; i_fillArrayLoop++ ) {
		// this converts an integer to a char !!! only works for the numbers 0 - 9
		c_digits_ary[i_fillArrayLoop] = (unsigned char)(i_fillArrayLoop + '0');
	}

	/* find prohibited digits */
	for ( i_fillArrayLoop = 0; i_fillArrayLoop < i_numberArraySize ; i_fillArrayLoop++ ) {
		/**********************************************************/
		/* we used the c_maxNumbers array earlier to find the     */
		/* maximum number of digits in this case it was 99999 we  */
		/* are now going to use the same variable for a different */
		/* purpose so let's reset it first                        */
		/**********************************************************/
		memset( c_maxNumbers_ary_ptr, 0x00, i_numberOfDigits );
		// this is one way to convert an integer to a c_str (c string)
		sprintf( c_maxNumbers_ary_ptr, "%d", i_withNumbers_ary_ptr[i_fillArrayLoop] );

		/***********************************************************/
		/* the reason that we changed the integer to a c_str is so */
		/* that we could check to see if a a digit in our list of  */
		/* digits contains one of the digits that we would like to */
		/* search for permutations for, we are replacing that      */
		/* digit with a random letter so that it isn't included in */
		/* our list of banned ints                                 */
		/***********************************************************/
		// strstr is used to check to see if c_digits_ary contains c_maxNumbers_ary_ptr
		// it gives us the position of that number
		if ( c_charCheck_ptr = strstr( c_digits_ary, c_maxNumbers_ary_ptr ) ) {
			// replace a number that is to be included in permutations with a random
			// character, this time I did 'N' but any char that is not a digit 0 - 9 is fine
			*c_charCheck_ptr = 'N';
		}
	}

	/* all numbers from 1 to max numbers */
	for ( i_fillArrayLoop = 0; i_fillArrayLoop <= i_numberLimit; i_fillArrayLoop++ ) {
		i_numberList_ary_ptr[i_fillArrayLoop] = i_fillArrayLoop;
	}

	/* this is where we check to see if a number fits in our permutations list */
	for ( i_fillArrayLoop = 0; i_fillArrayLoop <= i_numberLimit; i_fillArrayLoop++ ) {
		// this is setup for our checks
		b_match = true; // this equals true meaning there's a match the second that there is no match it's false
		// clear c_maxNumbers_ary_ptr again to so we can use it for something else
		memset( c_maxNumbers_ary_ptr, 0x00, i_numberOfDigits );
		// convert a number from our list of numbers to a string
		sprintf( c_maxNumbers_ary_ptr, "%d", i_numberList_ary_ptr[i_fillArrayLoop] );

		/**********************************************************/
		/* here we compare each digit to the number in            */
		/* c_maxNumbers_ary_ptr just as a side note the sizeof    */
		/* function returns the size of something, in this case   */
		/* the size of an array, but it can return the size of    */
		/* anything.  right night it's returning the size of      */
		/* c_digits_ary which is 11... why 11? because in c       */
		/* strings usually have to end with a null terminator,    */
		/* the character '\0' so c_digits_ar is actually the      */
		/* string [0123456789\0] we don't want to include the '\  */
		/* 0' in our check so we get the sizeof(c_digits_ary) - 1 */
		/**********************************************************/
		for ( i_checkPermutations = 0; i_checkPermutations < sizeof(c_digits_ary) - 1; i_checkPermutations++ ) {
			// put a digit into c_digitAsString_ary[0]
			c_digitAsString_ary[0] = c_digits_ary[i_checkPermutations];
			
			/***********************************************************/
			/* we used strstr before, this time we are using it to     */
			/* determine if the number in c_maxNumbers_ary_ptr is a    */
			/* valid permutation,  when finds c_digitAsString_ary in   */
			/* c_maxNumbers_ary_ptr it returns a value which is not 0  */
			/* or NULL,  that makes our if statement true meaning that */
			/* c_maxNumbers_ary_ptr is not a valid permutation         */
			/***********************************************************/
			if ( strstr( c_maxNumbers_ary_ptr, c_digitAsString_ary ) ) {
				b_match = false;
				break;
			}

		}

		/* one last check if the permutation is true does it contain our */
		/* required number?                                              */
		if ( b_match ) {
			if ( strstr( c_maxNumbers_ary_ptr, c_requiredNumber_ptr ) ) {
				i_matchList_ary_ptr[i_matchCount] = atoi( c_maxNumbers_ary_ptr );
				i_matchCount++;
			}
		}

	}

	/* if you would like to output the numbers to a file or print them to a screen */
	/* a loop should be made here to print all the number in i_matchList_ary_ptr   */
	//for () {
		// operations
	//}

	return( i_matchCount );
}

int main()
{

	int i_withNumbers[] = { 1,2,3,4,5 }; // numbers to be used in finding permutations

	/* see function above for explanation of parameters */
	int matches = CountPermutations_func( 6, i_withNumbers, sizeof(i_withNumbers)/sizeof(int), "1" );

	return( 0 );

}

BTW: There are a few safeties that I didn't add to the code... for example if someone tries to find permutations for something bigger than a value called MAX_INT, basically the biggest interger a system can hold. I also didn't design it to work with multiple required numbers. It will only do one. There are probably a few other things, but this is basically it.

If you have any questions feel free to ask anytime.

[claytonl]

Hmmm I tried 3 different compilers with no luck. They all seem to have the same problem:

test.cpp: In function ‘int CountPermutations_func(int, int*, int, char*)’:
test.cpp:29: error: ‘memset’ was not declared in this scope
test.cpp:38: error: ‘atoi’ was not declared in this scope
test.cpp:74: error: ‘strstr’ was not declared in this scope
test.cpp:119: error: ‘strstr’ was not declared in this scope
test.cpp:129: error: ‘strstr’ was not declared in this scope
test.cpp: In function ‘int main()’:
test.cpp:152: warning: deprecated conversion from string constant to ‘char*’

I was hoping to compile it to see it in action. Any ideas? What do you use to compile?

[nexocentric]

That is a sign that some headers weren't included.

For memset and strtstr

#include <string.h>  or #include <cstring>
#include <stdlib.h> or #include <cstdlib>

those should clear right up.

Since i was using VC++ Express i didn't need to include them. I should have done this on my unix machine.