'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 |
|---|
