CODEWITHSUNDEEP
algorithmcombinationscombinatorics
Oleg
Oleg

Reputation: 3200

Generate all possible splittings

I am looking the fastest algo for the following task. I have some array

[a,b,c ... ]

and I need to generate some equally random array of arrays that contains all elements of main array, something like this:

Input [1 2 3 4 5 ] => [ [1 2 ] [3 4 ] [ 5 ] ]

Straitforward solution is to generate all splittings and randomly choose one of them . This solution guarantees that all splittings will be chosen with equal probability. But Its too slow for big numbers. Is there the other possibility to create this splitting?

Upvotes: 1

Views: 70

Answers (1)

user2357112
user2357112

Reputation: 280564

For each possible splitting point, randomly decide whether or not to split there. For example, in Python:

import random

def random_split(input_list):
    result = [[]]

    # Assume input is nonempty, since it's not clear what the result should
    # be if the input is empty.
    result[-1].append(input_list[0])

    for item in input_list[1:]:
        if random.randrange(2):
            # Split here.
            result.append([])
        result[-1].append(item)

    return result

Upvotes: 2

Related Questions