Part of a program I am working on needs to output a 4 digit number, in which none of the digits are repeating. i.e 1135 and 1676 are not valid. Also, there can be no "0" in the 4 digit number.
I defined an array:
and am trying to figure out a way to shuffle it and output a[0], a[1], a[2], and a[3].Code:int a ={1, 2, 3, 4, 5, 6, 7, 8, 9}; for(i=0; i<4; i++) printf("%d", a[i]);
All advice is appreciated. Thanks in advance.
What you need is a "card shuffle". There are lots of variations but it can be done in a very simple loop...
Code:// 100% untested #define MAX 10 // could be any number int array[MAX]; int temp; int swap; // create sequence srand(time(0)); // shuffle in loop for (int i = MAX; i > 0; i--) { swap = rand() % i; temp = array[i]; array[i] = array[swap]; array[swap] = temp; }
Take your array down to just 4 elements.
Now imagine each element is a wheel on an odometer, beginning values of 1234:
Now, 'drive' the wheels around, assigning digits of 1-9, but always working through the right most wheel, just like a real odometer:
1234
1235
1236
1237
1238
1239
1240
1241
1242
will produce every possible number. Test each number and see which one's are valid. If they are, output them, if not continue looping, until 9876.
Each wheel can be a nested loop:
AndCode:for(w1 = 1;w1<10;w1++) { for(w2 = 2;w2<9;w2++) { etc., add two more wheels. } }Welcome to the forum, ISUFrosh!
If you only need "some" numbers, and they don't have to be in order, then the shuffling way is fine. This is more when you need ALL the numbers, and possibly, in order.
Yes, I confess, I use this logic in my Sudoku solving program, so every digit among the candidate digits for that square, has to be checked.
Last edited by Adak; 11-02-2010 at 11:34 PM.
Wouldn't you want to go from 1 to 9 (inclusive) on all the indexes? You'll reject a lot of numbers starting with 11xx, but always starting at 2 from the second number means you'd jump from 1999 to 2211, missing valid combinations like e.g. 2134.
You can also do this recursively. Something like (totally untested code and likely buggy code)
Initially set valid to all 1s and call it with pos = 0.Code:permute (unsigned char valid[10], unsigned char num[4], int pos) { if (pos == 4) { /* If it's a 4 digit number print it and return */ printf ("%d%d%d%d\n", num[0] ... num[3]); return; } for (i = 0; i < 10; i++) { /* For each valid remaining digits, display all of the numbers which include each of those digits at the current position. */ if (valid[i]) { valid[i] = 0; num[pos] = i + 1; permute(valid, num, pos+1) valid[i] = 1; } } }
It's overkill for this case, but nice because you can include/exclude all sorts of stuff by varying how valid[] is set up.
I think i figured something out, but can't get it to work.
I have no clue why, but all i get is 1 digit, i.e. 1 or 5 or 3, and the command prompt is froze.Code:#include <stdio.h> #include <time.h> int main() { int a[4]; srand(time(NULL)); int i,j, k=1; /*Initializes a[i], then compares it to a[j]. If they are equal, it should start over the while loop with the same value fro 'i' until it is not equal to a[j]*/ for(i=0;i<4;i++){ while(k){ a[i]=rand()%10; k=0; for(j=0;j<i; j++){ if(a[i] == a[j]); k++; } } k=1; printf("%d", a[i]); } system("pause"); }
Got it!!
[code]
a[0]=rand()%10;
for(i=1; i<4; i++){
a[i] = rand()%10;
int temp = i;
for(j=0; j<temp; j++){
if(a[j]==a[i])
i--;
}
} [\code]
Last edited by ISUFrosh; 11-03-2010 at 04:37 PM.
Exactly so. The 1234 was just a starting place.Wouldn't you want to go from 1 to 9 (inclusive) on all the indexes? You'll reject a lot of numbers starting with 11xx, but always starting at 2 from the second number means you'd jump from 1999 to 2211, missing valid combinations like e.g. 2134.
I'm not sure how many 4 digit numbers our guy needs, and whether they benefit by being in order, etc.
That's a Freshman for ya!
Last edited by Adak; 11-03-2010 at 08:34 PM.
