'How many combinations this bin packing problem has?

Let's say we have a set of 100 videos that contain 10 to 30 frames, and we want to group them in n groups such as the total number of frames of each group are approximatively equal. Moreover, every frame belonging to one video has to be part of a unique group.

First, is it possible to know the number of possible combinations knowing that the order has no importance?
For simplicity, let's say we have only 6 videos {1,2,3,4,5,6} with an equal number of frames and we want to group them into n=2 groups.

0 -> (1,2,3) (4,5,6)
1 -> (1,2,4) (3,5,6)
2 -> (1,2,5) (3,4,6)
3 -> (1,2,6) (3,4,5)
4 -> (1,3,4) (2,5,6)
5 -> (1,3,5) (2,4,6)
6 -> (1,3,6) (2,4,5)
7 -> (2,3,4) (1,5,6)
8 -> (2,3,5) (1,4,6)
9 -> (2,3,6) (1,4,5)

So by hand, I found 10 possible groups.
Is there a formula that describes this process?

Second, is there a way to solve this problem without brut force?

My first guess is to randomly create n groups and choose the best group such as its number of frames per group standard deviation is the lowest.

Here is my brute force solution in Python:

import numpy as np

np.random.seed(42)

n_group = 7
nr_videos = 100
iterations = 1000

video_dataset = np.random.randint(10,30, nr_videos)

# Total number of frames
total_frames = np.sum(video_dataset)

# Optimal number of frames per bin
target_frames_per_bin = total_frames/n_group

# Array containing every standard deviation
std_array = np.zeros(iterations, dtype=float)

# Array containing the number of frame for each bin at one iteration
nr_frames_per_bin = np.zeros(n_group, dtype=int)

for i in range(iterations):
    # Shuffle the video dataset
    seed = i
    np.random.seed(i)
    new_video_dataset = np.array(video_dataset)
    np.random.shuffle(new_video_dataset)

    # Reset the array
    nr_frames_per_bin *= 0

    # Pack each bin consecutively
    bin_n = 0
    for j in range(nr_videos):
        if(nr_frames_per_bin[bin_n] > target_frames_per_bin):
            bin_n += 1
        nr_frames_per_bin[bin_n] += new_video_dataset[j]

    # Compute the std for the current bin
    std_array[i] = np.std(nr_frames_per_bin)

best_seed = np.argmin(std_array)
best_std = std_array[best_seed]

print("Best iteration:", best_seed)
print("Best std:", np.round(best_std,2))

Please let me know if I'm clear enough. Thanks for your help.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source