2

Suppose that you have a range of numbers from 0 to N that you want to randomly separate in groups of max M sequential numbers. This is easily done with a bitmap and a random number generator, but it is not space efficient for very large instances of N.

So, what I want is a generator that, given a number N and M, will start producing non-overlapping groups in a random order and with random size, with less than O(N) space efficiency.

E.g. for N = 7 and M = 3, a valid output is the following:

4
1, 2
3
5, 6, 7
0

Does anyone know an algorithm that can help in producing such an output?

  • I guess you meant less than O(N) space efficiency, not O(n)? And if so, what is your idea of storing the result (since you need typically an array of size N for the result)? – Doc Brown Dec 1 '14 at 9:29
  • It's not clear to me what random distribution you expect to achieve. For example, if N is 2 and M is 3, there are six possible initial groups that could be returned (0, 0..1, 0..2, 1, 1..2, 2). Should they all have the same probability? Because if you used an algorithm that first picked a random unused starting point and then picked a random possible length, you would end up with uneven probabilities for the six possible groups. – JS1 Dec 1 '14 at 9:33
  • Yes, O(n) was a typo. As for the groups that the generator produces, they will not be stored somewhere. Each group will be used for some calculations when the generator produces it and then we can forget about it. – nine Dec 1 '14 at 9:35
  • @JS1: In your example, N is 2, therefore the range is from 0 to 2. In this case, we have the following possible outputs: (0, 1, 2) || (1, 2), (0) || (0, 1), (2) || (1), (0), (2) || ... – nine Dec 1 '14 at 9:37
  • Yes there are 11 total possible partitions with N = 2. Do you need them to have equal probability? – JS1 Dec 1 '14 at 9:45
1

I created a partitioning program with space usage O(1) but running time O(N^2). You can find the source code here. In the comments there is a good explanation of the shuffling algorithm used.

The key part of this program is the shuffling step, which is the step that takes O(N^2) time. Doc Brown asked "how can you shuffle N elements in less than O(N) space"? I extracted the shuffling logic and created a separate program which is listed below.

To get the full explanation, please refer to the source code linked above. The following is a brief explanation:

The shuffling function simulates a Fisher-Yates shuffle, where you swap the array[0] with array[r], where r is a random number in the range [0..N-1]. Then you swap array[1] with array[r], where r is a new random number in the range [1..N-1]. You keep moving down the array, swapping random elements, until you reach the end of the array.

To use O(1) space, there is no array. Instead, for each new random element that we select, we need to replay the previous swaps in backwards order in order to figure out where the array element really came from. In essence, we pick a random element, and then we undo the swaps that came before it to determine where the original position of the element was. We can replay the previous swaps by simply reseeding the random number generator back to a previously saved seed.

Edit: After posting this solution, I found this stackoverflow question which lists some better ways to create a permutation of N numbers in constant space. So if you substitute one of those solutions in for my shuffling function, you can do better than O(N^2) time and still use O(1) space.

/* Given a number N, shuffle the elements from 0..N-1 and print them. */
/* This algorithm uses O(1) space but uses O(N^2) time.               */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

static void shuffle(int n);

int main(int argc, char *argv[])
{
    if (argc < 2) {
        printf("Usage: shuffle N\n");
        exit(0);
    }

    shuffle(atoi(argv[1]));
    return 0;
}

static void shuffle(int n)
{
    uint32_t seedOriginal = time(NULL);
    uint32_t seed         = 0;
    int      i            = 0;
    int      j            = 0;
    int      slot         = 0;

    for (i=0;i<n;i++) {
        seed = seedOriginal;
        srand(seed);

        // Skip n-i-1 random numbers.
        for (j=n-i-1;j>0;j--)
            rand();

        // Select an array slot from [i..n-1].
        slot = i + (rand() % (n - i));

        // Find out what that slot corresponds to in the original order.
        // We do this by backtracking through all the previous steps.
        for (j=i-1;j>=0;j--) {
            int r = j + (rand() % (n - j));

            // Every time we see the slot we are looking for, we switch
            // to looking for slot j instead, because at this previous step
            // we swapped array[j] with array[slot].
            if (r == slot)
                slot = j;
        }

        // Slot is now the correct element we are looking for.
        printf("%d\n", slot);
    }
}
  • I finally got round to reading and running your answer. While the time complexity is quadratic, the provided code is well documented and the algorithm behind it is very interesting. Thanks for all your effort. I'll mark it as the accepted answer, having in the back of my mind that there may actually be no answer within the provided constraints for this problem. – nine Jan 8 '15 at 16:21
1

Actually generating random non-overlapping groups in a random order would be a pain in the neck. For example, you'd selected a random "start"; then search existing groups to make sure start is usable and find the "highest possible end" for that start; then select a random "end" that's between "start" and "highest possible end". As long as you're selecting a random "start" you can't avoid some sort of search.

Instead, split it into 2 parts: generate random non-overlapping groups in ascending order; then shuffle them to so they end up in random order.

Generating random non-overlapping groups in ascending order is simple. Each group begins where the previous group ends, and you just need a random length.

  • How will you random shuffle N elements with less than O(N) space? – Doc Brown Dec 1 '14 at 13:32
  • @Doc Brown is right. The approach of two passes that you propose will need to store the groups somewhere, which violates the less than O(N) constraint. – nine Dec 1 '14 at 16:11
  • Given "a range of numbers from 0 to N", where K is the number groups; my solution would be O(K) and not O(N). – Brendan Dec 15 '14 at 16:09
  • @Brendan: Maybe I wasn't clear, but I was not referring to the time complexity but to the space complexity. Your two passes proposal will need an intermediate step where the groups will be stored. This will take O(N/M) space, which for small M can be considered as O(N) space, and thus violating the less than O(N) space constraint. – nine Dec 22 '14 at 13:17
  • @nine: For small M it can be considered as O(N), and for large M (e.g. M = N*2) it can be considered O(1). Woot - it's O(1)! :) – Brendan Dec 26 '14 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.