I need help with the following function :::

[omarelmasry]

I am making a c++ program and i need a function that does the following:

IF u have an n (e.g: 4) digit number (IN THE FORM OF AN ARRAY) , each digit can take the vlaue from 0 to m (e.g: 5) and can exist more than once in the number (EACH DIGIT IS AN ELEMENT IN THE ARRAY)..

The number starts by the minimum value that the digits can form...

The number enters in a loop which increases the number, every iteration, to generate the NEXT BIGGER number that consists of the same digits and prints the number...

NOTE::: I dont want the function to increase the number every time by ONE and checks that the digits are there.... this will be silly :p...
I asked this question to find the fastest algorithm ....

Thanks in advance :)

[Alex Edwards]

I am making a c++ program and i need a function that does the following:

IF u have an n (e.g: 4) digit number (IN THE FORM OF AN ARRAY) , each digit can take the vlaue from 0 to m (e.g: 5) and can exist more than once in the number (EACH DIGIT IS AN ELEMENT IN THE ARRAY)..

The number starts by the minimum value that the digits can form...

The number enters in a loop which increases the number, every iteration, to generate the NEXT BIGGER number that consists of the same digits and prints the number...

NOTE::: I dont want the function to increase the number every time by ONE and checks that the digits are there.... this will be silly :p...
I asked this question to find the fastest algorithm ....

Thanks in advance :)

so what you're trying to do is create a sorting algorithm that, through each pass, will create a number that was bigger than the previous number specified.

I believe this is what you mean--

// before function call
[0][0][1][2][3]


// after one function call

[0][0][1][3][2]


//after two calls

[0][0][2][1][3]

//after three calls

[0][0][2][3][1]

// after four calls

[0][0][3][1][2]

// after five calls

[0][0][3][2][1]

// after six calls

[0][1][0][2][3]

//after seven calls

[0][1][0][3][2]

// after eight calls

[0][1][2][0][3]

// after nine calls

[0][1][2][3][0]

// after ten calls

[0][1][3][0][2]

// after eleven calls

[0][1][3][2][0]

//after twelve calls

[0][2][0][1][3]

//...

Is this the correct logic?

[omarelmasry]

Yes ... that's what I mean....
but now i think it will be better if the loop is external (not in the function) ....
The function can take the any number as a parameter and generate the next bigger number
Please reply ....and Thanks for ur help!!!

[Lerner]

I'd suggest you break down the problem into smaller steps. The first step I would do is to develop an algorithm to generate the next highest number for n of a given, small value, say 3 or 4. Then I'd try to generalize that process. Given the unknown size of the array the generalization may take the form of a recursive function or maybe use some of the concepts of dynamic programming or some other technique to handle an unknown number of repititions at run time.

[Alex Edwards]

I'd suggest you break down the problem into smaller steps. The first step I would do is to develop an algorithm to generate the next highest number for n of a given, small value, say 3 or 4. Then I'd try to generalize that process. Given the unknown size of the array the generalization may take the form of a recursive function or maybe use some of the concepts of dynamic programming or some other technique to handle an unknown number of repititions at run time.

If possible, I'd also suggest using a vector instead of a pointer =P

[VernonDozier]

I wouldn't start coding it yet. Write the algorithm out on paper first till you get a good feel for it. This is as much of a mathematics/statistics problem as it is a computer programming problem. First realize that in a number like:

42276

you are dealing with four possible digits, not eight, so if it was me, at least in the beginning, i would rewrite it, at least temporarily, as:

10032

For me it's just easier to look at it this way and go from there. You won't code it like this, but when I'm working it out on paper in the beginning, I change the digits to 0,1,2,3. You'll need to change the digits later, of course, but I think it's easier this way in the beginning. Others may not. Start with the most significant digit (1). 1 will stay the same if and only if the remaining digits are NOT sorted in descending order. If they ARE sorted in descending order, the most significant digit will increase by 1. In that case, the remaining digits should be sorted in ASCENDING order and you are done with that iteration.

In the case of 10032, the numbers to the right of the most significant digit (0032) are NOT in descending order, so 1 stays the same. Now look at the remaining digits (0032) and peel off the most significant digit (0). Look at the remaining digits (032).

Is 032 in descending order?

No, so the Most Significant Digit (0) , stays as it is, so we have the first two digits of our next number (10) and three remaining digits:

032

Peel of the Most Significant Digit (0). 32 remains.

Is 32 in descending order? Yes. Therefore the Most Significant Digit (0) must increase. The next lowest digit after 0 here is 2, so the most significant digit will be 2 and the leftover digits are 0 and 3, so we have the three leftmost digits:

102

and the remaining digits, 0 and 3. Sort the remaining digits in ASCENDING order and you get:

03

Combine the two number fragments and you get

10203

which is the number after

10032

which was the goal from the beginning. You have to change the 0,1,2,3 back to 2,4,6,7 since those are your original digits. I don't suggest that you CODE it so you change the digits. Keep them the same. I just thought it was easier to show in this post using 0,1,2,3 rather than 2,4,6,7. Anyway, that's one algorithm. You could also approach it from the Least Significant Digit side, but regardless, I'd say you need to write a function that can sort digits in ascending and descending order as well as a boolean function that checks whether the digits are already IN ascending or descending order. You may also need a function that takes an array of digits and a digit to be removed and returns the remaining digits.

That's one way to approach the problem. I'm sure there are other ways too.

[Alex Edwards]

The uglier way of doing this would be iterating a similar number adjacent to this one and comparing all possible "combinations" of the number to the iterated number.

Not only would you lose time from the iteration but from the constant juggling of numbers just to get a match!

[VernonDozier]

The uglier way of doing this would be iterating a similar number adjacent to this one and comparing all possible "combinations" of the number to the iterated number.

Not only would you lose time from the iteration but from the constant juggling of numbers just to get a match!

Actually, looking back at the OP's original post:

The number starts by the minimum value that the digits can form...

The number enters in a loop which increases the number, every iteration, to generate the NEXT BIGGER number that consists of the same digits and prints the number...

The best approach would NOT be to take a number and figure out the next biggest number from the previous number. omarelmasry needs ALL combinations and he/she needs them in order. If not careful, an awful lot of overhead and repeated calculations are involved in calculating the next biggest number from the previous number. If you know you're producing all of them from the very beginning and that you need them to be in order from the very beginning, the approach may well be different.

[Alex Edwards]

Actually, looking back at the OP's original post:

The best approach would NOT be to take a number and figure out the next biggest number from the previous number. omarelmasry needs ALL combinations and he/she needs them in order. If not careful, an awful lot of overhead and repeated calculations are involved in calculating the next biggest number from the previous number. If you know you're producing all of them from the very beginning and that you need them to be in order from the very beginning, the approach may well be different.

I'm aware of that - the original poster said that he wanted the fastest way and that he didn't want to increment by one each time. I was simply stating that I couldn't find another way of doing this more efficiently than the method you mentioned.

However now that I think about it, there is another (possible) alternative. You could generate n * n arrays (where n is the amount of numbers in the array), each with a different combination of the values in the array then string-stream the values (or concatenate them) then store them in a double pointer (a char** pointer), sort them, delete any repeat numbers and return the sorted char** pointer.

Edit: A Vector of Strings may be more ideal than a char** pointer