algorithm challenge

Is this a school assignment? It is of good manners to state that outright in your first post.

no it's from my mind

Shuffle algorithms can handle this easily, although those may fail with sufficiently large N and K that won't fit in memory. Several unbiased O(n) shuffle algorithms exist, such as the Fisher-Yates shuffle. If you're using C++ there is an implementation of that std::shuffle() which was previously known as std::random_shuffle() if you're using an old compiler.

Even if you can't hold N in memory, if you could hold a count of N values in an array then it becomes your index into N. Add values from 0 to N-1 as all index values, shuffle them, and pick K values.

If you can't reasonably make a list of length N, this comes to mind:

1. Select random offset numbers. Select K numbers; pull from 0 to N-1, then from 0 to N-2, then from 0 to N-3. etc. Use a non-biased algorithm for this.
2. Compute the index values. Iterate through the offset numbers. The initial value is the random number, then iterate over the prior index values in ascending order; if an existing index value is lower than the value you are considering, increment your current value under consideration. When you've incremented up to the current value, it becomes the new index. In other words, the offset value means to advance that many unused numbers.
3. Look up the index values from pool N for the final list.

As an example of N=15 and K=5:

1. Using a random number generator I get the following five values from the first step: { 1, 9, 4, 11, 6 }

2. Next I compute the index values:

Index 1. { 1 }

Offset 9 finds it is greater then index 1, so becomes index 10 { 1, 10 }

Offset 4 finds it is greater than index 1, 10 is greater, so becomes index 5. { 1, 5, 10 }

Offset 11 finds it is greater than 1, 5, and 10, so becomes index 14. { 1, 5, 10, 14 }

Offset 6 finds it is greater than 1 and 5, so becomes index 8. { 1, 5, 8, 10, 14 }

3. Look up the values N[1], N[5], N[8], N[10], N[14]. This is your result.

If ordering were important, maintain a parallel ordered list where each index is added in the same order they were generated from the initial offset list.

And for N=15 and K=15 so you should see every item:

Offset numbers { 1 9 4 11 6 4 6 7 2 3 2 0 2 0 0 }

Index values as they grow:

(unused offset 1) 1
(+9) 1 10
(+4) 1 5 10
(+11) 1 5 10 14
(+6) 1 5 8 10 14
(+4) 1 5 6 8 10 14
(+6) 1 5 6 8 10 11 14
(+7) 1 5 6 8 10 11 13 14
(+2) 1 3 5 6 8 10 11 13 14
(+3) 1 3 5 6 7 8 10 11 13 14
(+2) 1 3 4 5 6 7 8 10 11 13 14
(+0) 0 1 3 4 5 6 7 8 10 11 13 14
(+2) 0 1 3 4 5 6 7 8 10 11 12 13 14
(+0) 0 1 2 3 4 5 6 7 8 10 11 12 13 14
(+0) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

If you want that in random order, preserve the order of the offsets: { 1 10 5 14 8 6 11 13 3 7 4 0 12 2 9 }

Or if you prefer to see it from the perspective of the UNUSED pool:

(position 1) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
(9) 0 2 3 4 5 6 7 8 9 10 11 12 13 14
(4) 0 2 3 4 5 6 7 8 9 11 12 13 14
(11) 0 2 3 4 6 7 8 9 11 12 13 14
(6) 0 2 3 4 6 7 8 9 11 12 13
(4) 0 2 3 4 6 7 9 11 12 13
(6) 0 2 3 4 7 9 11 12 13
(7) 0 2 3 4 7 9 12 13
(2) 0 2 3 4 7 9 12
(3) 0 2 4 7 9 12
(2) 0 2 4 9 12
(0) 0 2 9 12
(2) 2 9 12
(0) 2 9
(0) 9

if you want to go crazy, you can use RSA encryption. You'd create K rings (basically K prime numbers > N) on initialization.

https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n

Every round you call "rand" once, feed the resulting number into the rings (modulo multiplication), and you should get K numbers. You might get results >N (as you have to pick rings that are bigger), but then you just repeat the loop until you have K different and

A simpler version would be to use some hashing algorithm with K seeds %N (but that's like writing your own randomizer, that's why I'd pick RSA, it's just math, not random obscurance).

I'm pretty sure that would generate a biased distribution rather than a random distribution. Also, the multi-round RSA thing is going to be rather complex.

11 minutes ago, frob said:

I'm pretty sure that would generate a biased distribution rather than a random distribution. Also, the multi-round RSA thing is going to be rather complex.

RSA, biased? Nope, it's not, otherwise it would be a security issue and you could use statistical methods to approach a solution.

Multi round depends on the likeliness of a collision by randomly picking numbers, yet with N within register size, it's just a mul + modulo. Pretty cheap on modern CPUs, cheaper than indexing randomly in memory.

#include <iostream>

int C[20][20] = {0};

void print_combination(int r, int n, int k) {
  if (k == 0)
    return;
  bool selected = (r < C[n-1][k-1]);
  if (selected) {
    print_combination(r, n-1, k-1);
    std::cout << n << ' ';
  }
  else
    print_combination(r - C[n-1][k-1], n-1, k);
}

int main() {
  // Initialize combinatorial numbers table                                                                                               
  for (int i = 0; i < 20; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = C[i-1][j-1] + C[i-1][j];
  }

  // Loop over all combinations                                                                                                           
  for (int x = 0; x < C[6][3]; ++x) {
    print_combination(x, 6, 3);
    std::cout << '\n';
  }
}

For your original question, call `print_combination(random_number, 6, 3)'.

Also see the constraint: - N and K are very big - I mean, you can't iterate all the possibilities

3 minutes ago, frob said:

Also see the constraint: - N and K are very big - I mean, you can't iterate all the possibilities

If you were referring to my code, the iteration over all possibilities is for demonstration purposes only. The function print_combination would work for large N and K (as long as you can handle numbers as big as C[N][K], which is assumed as part of the original post).

EDIT: It can also be done non-recursively, but I think the code is easier to understand in this version.

Well if you can only call the random function once wouldn't any technique just be a play on manipulating the random number using integer positions of said number and what not? Interesting though, makes me think that all games are really just manipulations of the clock.

@alvaro , even if we don't care of memory, if N and K are very big it could take years to fill the C[N][K] array . But for decent N and K it seems it's working

@frob, I had no knowledge on the Fisher-Yates shuffle, but it looks like it's using several random numbers... However you can tell me that I told "Random function can manage numbers of any size you want", so we can generate small random numbers from a big number.
Concerning your algorithm, I assume it's working correctly even if some indices are equal in the first step, so I think it would work too, with a very big initial random to generate the list of indices.

In all the cases, it seems we need something big to initialize the algorithm. I don't know if we can do it, only with 1 initial random number R between 1 and binomial(N,K), I mean this is the number of possibilities. and then with a smart algorithm, have the Rth combination. (without iterating throw all combinations).

I'm currently not near a PC to provide an implementation sample, but take a look at the factorial number system/ lehmer code; that should point you into a pretty common direction to tackle that kind of problem:

https://en.wikipedia.org/wiki/Factorial_number_system

https://en.wikipedia.org/wiki/Lehmer_code

wow very interesting, I just read quickly the 2 articles. I think you pointed exactly what I was searching. I'll try to find more time later to take a closer look, and implement something.

+1 for @frob's suggestion of a modified Fisher-Yates. When reading the problem, his solution was the one I was thinking about (in less detail though).

On 2/27/2018 at 11:58 AM, RichardGe said:

- you can call Random function only 1 time. ( this Random function can manage numbers of any size you want )

This makes it easy. Just use the random to generate a noise sample large enough to cover for all the numbers.

I decided to use python, there will also need to be some way to work with Bigint, python can but not while converting. you could use an image or what ever kind of noise sample.

Also a kind of true random will be needed because random range keeps more between (0.3-0.7) but 0 and 1 are possible.

import random

def GetNoise(InN,InK):
    NoiseRangeMin = InN * int(InK)
    NoiseRangeMin = "1" + ("0" *( len(NoiseRangeMin)-1))
    NoiseRangeMax = "1" + ("0" *( len(NoiseRangeMin)))

    NoiseSample = random.randrange(int(NoiseRangeMin),int(NoiseRangeMax))
    #print(NoiseSample)
    return str(NoiseSample)

def TranslateNoise(InN,InK,InNoise):
    LastDigit = int(InN[len(InN)-1])
    index = int(InK)
    OutStr = ""
    while index > 0:
        index -= 1
        #Get as reverse for easy out
        OutInt = int(InNoise[index*len(InN) :(index*len(InN))+ (len(InN))])
        #If the number is 3 digits we / by 999 this way each number is part of a base
        #Because the max digit is 9 every noise digit is a 9th of the N digit
        #If N is 1 there is a 50% chance that N =1 or N = 0
        numberSize = int(InN) / int("9"*len(InN))
        OutInt = round(numberSize * OutInt)
        print("Ball"+ str(index)+ ":" + str(OutInt))



N = input("N?:" )
K = input("K?:" )

Noise = GetNoise(N,K)
TranslateNoise(N,K,Noise)

Be warned! Large numbers take some time.

Assuming N is max size of a number and K = ball the print will be like this:

N = 9 and K = 2 : (9,9) is max and (0,0) is min

N = 13414341 K = 123 : Makes balls ranging from 0 - 13414341 in base 10 step.

With floats or doubles you can get more precise, when using images you can use bit depth for precision.

Still seems like an awful lot of extra work.

As demonstrated above, this can be done with linear performance equal to K (the number of desired items). No need to shuffle the entire set of N, nor generate fancy noise. Generate K numbers, one pass through the set of K generates your values, and you're done.

Thus it doesn't matter if there are 50 values in N or trillions of values in N. When all you need is K values you only process K values. No extra work, no extra shuffling of the data, no worry about the same value being picked twice even if K==N.

On 3/5/2018 at 7:11 AM, frob said:

As demonstrated above, this can be done with linear performance equal to K (the number of desired items).

I've tried it and can't get it to work. Any chance you can share a sample code? Sounds like it could be very handy for fast random results.

No source code, just the algorithm as stated.