I'm trying to make a get_random_4digit function that generates a 4 digit number that has non-repeating digits and digits ranging from 1-9 while only using int's, if, while and functions, so no arrays etc.
This is the code I have but it is not really working as intended, could anyone point me in the right direction?
int get_random_4digit() {
int d1 = rand() % 9 1;
int d2 = rand() % 9 1;
while (true) {
if (d1 != d2) {
int d3 = rand() % 9 1;
if (d3 != d1 || d3 != d2) {
int d4 = rand() % 9 1;
if (d4 != d1 || d4 != d2 || d4 != d3) {
random_4digit = (d1 * 1000) (d2 * 100) (d3 * 10) d4;
break;
}
}
}
}
printf("Random 4digit = %d\n", random_4digit);
}
CodePudding user response：
There are 9 possibilities for the first digit, 8 possibilities for the second digit, 7 possibilities for the third digit and 6 possibilities for the last digit. This works out to "9*8*7*6 = 3024 permutations".
Start by getting a random number from 0 to 3023. Let's call that P. To do this without causing a biased distribution use something like do { P = rand() & 0xFFF; } while(P >= 3024);.
Note: If you don't care about uniform distribution you could just do P = rand() % 3024;. In this case lower values of P will be more likely because RAND_MAX doesn't divide by 3024 nicely.
The first digit has 9 possibilities, so do d1 = P % 9 1; P = P / 9;.
The second digit has 8 possibilities, so do d2 = P % 8 1; P = P / 8;.
The third digit has 7 possibilities, so do d3 = P % 7 1; P = P / 7;.
For the last digit you can just do d4 = P 1; because we know P can't be too high.
Next; convert "possibility" into a digit. For d1 you do nothing. For d2 you need to increase it if it's greater than or equal to d1, like if(d2 >= d1) d2 ;. Do the same for d3 and d4 (comparing against all previous digits).
The final code will be something like:
int get_random_4digit() {
int P, d1, d2, d3, d4;
do {
P = rand() & 0xFFF;
} while(P >= 3024);
d1 = P % 9 1; P = P / 9;
d2 = P % 8 1; P = P / 8;
d3 = P % 7 1; P = P / 7;
d4 = P;
if(d2 >= d1) d2 ;
if(d3 >= d1) d3 ;
if(d3 >= d2) d3 ;
if(d4 >= d1) d4 ;
if(d4 >= d2) d4 ;
if(d4 >= d3) d4 ;
return d1*1000 d2*100 d3*10 d4;
}
CodePudding user response：
You should keep generating digits until distinct one found:
int get_random_4digit() {
int random_4digit = 0;
/* We must have 4 digits number - at least 1234 */
while (random_4digit < 1000) {
int digit = rand() % 9 1;
/* check if generated digit is not in the result */
for (int number = random_4digit; number > 0; number /= 10)
if (number % 10 == digit) {
digit = 0; /* digit has been found, we'll try once more */
break;
}
if (digit > 0) /* unique digit generated, we add it to result */
random_4digit = random_4digit * 10 digit;
}
return random_4digit;
}
Please, fiddle youself
CodePudding user response：
One way to do this is to create an array with all 9 digits, pick a random one and remove it from the list. Something like this:
uint_fast8_t digits[]={1,2,3,4,5,6,7,8,9}; //only 1-9 are allowed, 0 is not allowed
uint_fast8_t left=4; //How many digits are left to create
unsigned result=0; //Store the 4-digit number here
while(left--)
{
uint_fast8_t digit=getRand(9-4 left); //pick a random index
result=result*10 digits[digit];
//Move all digits above the selcted one 1 index down.
//This removes the picked digit from the array.
while(digit<8)
{
digits[digit]=digits[digit 1];
digit ;
}
}
You said you need a solution without arrays. Luckily, we can store up to 16 4 bit numbers in a single uint64_t. Here is an example that uses a uint64_t to store the digit list so that no array is needed.
#include <stdint.h>
#include <inttypes.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
unsigned getRand(unsigned max)
{
return rand()%(max 1);
}
//Creates a uint64_t that is used as an array.
//Use no more than 16 values and don't use values >0x0F
//The last argument will have index 0
uint64_t fakeArrayCreate(uint_fast8_t count, ...)
{
uint64_t result=0;
va_list args;
va_start (args, count);
while(count--)
{
result=(result<<4) | va_arg(args,int);
}
return result;
}
uint_fast8_t fakeArrayGet(uint64_t array, uint_fast8_t index)
{
return array>>(4*index)&0x0F;
}
uint64_t fakeArraySet(uint64_t array, uint_fast8_t index, uint_fast8_t value)
{
array = array & ~((uint64_t)0x0F<<(4*index));
array = array | ((uint64_t)value<<(4*index));
return array;
}
unsigned getRandomDigits(void)
{
uint64_t digits = fakeArrayCreate(9,9,8,7,6,5,4,3,2,1);
uint_fast8_t left=4;
unsigned result=0;
while(left--)
{
uint_fast8_t digit=getRand(9-4 left);
result=result*10 fakeArrayGet(digits,digit);
//Move all digits above the selcted one 1 index down.
//This removes the picked digit from the array.
while(digit<8)
{
digits=fakeArraySet(digits,digit,fakeArrayGet(digits,digit 1));
digit ;
}
}
return result;
}
//Test our function
int main(int argc, char **argv)
{
srand(atoi(argv[1]));
printf("%u\n",getRandomDigits());
}
CodePudding user response：
One variant could be to use one value, 0x123456789, and do a Fisher-Yates shuffle on the nibbles (the 4 bits that makes up one of the digits in the hex value). When the shuffle is done, return the 4 lowest nibbles.
Example:
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <time.h>
uint16_t get_random_4digit() {
uint64_t bits = 0x123456789; // nibbles
// shuffle the nibbles
for(unsigned idx = 9 - 1; idx > 0; --idx) {
unsigned ish = idx * 4; // index shift
// shift for random nibble to swap with `idx`
unsigned swp = (rand() % (idx 1)) * 4;
// extract the selected nibbles
uint64_t a = (bits & (0xFULL << ish)) >> ish;
uint64_t b = (bits & (0xFULL << swp)) >> swp;
// swap them
bits &= ~((0xFULL << ish) | (0xFULL << swp));
bits |= (a << swp) | (b << ish);
}
return bits & 0xFFFF; // return the 4 lowest nibbles
}
The bit manipulation can probably be optimized - but I wrote it like I thought it so it's probably better for readability to leave it as-is
You can then print the value as a hex value to get the output you want - or extract the 4 nibbles and convert it for decimal output.
int main() {
srand(time(NULL));
uint16_t res = get_random_4digit();
// print directly as hex:
printf("%X\n", res);
// ... or extract the nibbles and multiply to get decimal result - same output:
uint16_t a = (res >> 12) & 0xF;
uint16_t b = (res >> 8) & 0xF;
uint16_t c = (res >> 4) & 0xF;
uint16_t d = (res >> 0) & 0xF;
uint16_t dec = a * 1000 b * 100 c * 10 d;
printf("%d\n", dec);
}
CodePudding user response：
You could use a partial Fisher-Yates shuffle on an array of 9 digits, stopping after 4 digits:
// Return random integer from 0 to n-1
// (for n in range 1 to RAND_MAX 1u).
int get_random_int(unsigned int n) {
unsigned int x = (RAND_MAX 1u) / n;
unsigned int limit = x * n;
int s;
do {
s = rand();
} while (s >= limit);
return s / x;
}
// Return random 4-digit number from 1234 to 9876 with no
// duplicate digits and no 0 digit.
int get_random_4digit(void) {
char possible[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int result = 0;
int i;
// Uses partial Fisher-Yates shuffle.
for (i = 0; i < 4; i ) {
int rand_pos = i get_random_int(9 - i);
char digit = possible[rand_pos];
possible[rand_pos] = possible[i];
possible[i] = digit; // not really needed
result = result * 10 digit; // update result
}
return result;
}
EDIT: I forgot the requirement "while only using int's, if, while and functions, so no arrays etc.", so feel free to ignore this answer!
If normal C integer types are allowed including long long int, the get_random_4digit() function above can be replaced with the following to satisfy the requirement:
// Return random 4-digit number from 1234 to 9876 with no
// duplicate digits and no 0 digit.
int get_random_4digit(void) {
long long int possible = 0x123456789;
int result = 0;
int i;
// Uses partial Fisher-Yates shuffle.
i = 0;
while (i < 4) {
int rand_pos = get_random_int(9 - i);
int digit = (possible >> (4 * rand_pos)) & 0xF;
possible ^= ((possible ^ digit) & 0xF) << (4 * rand_pos);
possible >>= 4; // discard digit from possibilities
result = result * 10 digit; // update result
i ;
}
return result;
}
CodePudding user response：
You could use a linear feedback shift register. Check out this Computerphile video.