can someone please come up with a solution to this problem, in programming language of choice (preferably Python, but anything could be fine I guess):
I have various track length groups, let's say:
10:03
24:23
...
and source tracks themselves:
1:03
9:00
4:24
...
and I need to find pragmatically which tracks belongs to above length group. As in example first two tracks belong to first group as their sum length is equal to group length
Thanks in advance
edit: It's not my homework as that time is long gone (I'm over 30) but it's a problem I have, and I'm not a programmer. I'll have a look at itertools, thanks
edit2: Thanks for you suggestions. I made Python script and if works fine and fast for me. It's sure not optimized, but here is skeleton:
from itertools import combinations
tracks = [1,2,3,4,5,6,7,8,9]
group = 7
d_key, valid_tracks, possible_group =0, [], {}
for i in sorted(tracks):
if i < group: valid_tracks.append(i)
for j in range(len(valid_tracks) - 2):
for k in combinations(valid_tracks, len(valid_tracks) - 1 - j):
if sum(k) <= group:
if sum(k) == group:
d_key += 1
possible_group[d_key] = k
print possible_group
I'm glad I solved this, as tracking this by hand would take me more 开发者_StackOverflow中文版then my life-time, ha-ha
Look at the itertools module of Python:
http://docs.python.org/library/itertools.html
It supports to calculate all possible permutations() and combinations() of the tracks.
The rest is up to you (not doing your real homework).
This is a hard general NP-complete problem, known as Knapsack problem. You can check the wikipedia article for common approaches to its solution, but it would not be that easy or fast in general case. You could also check the knapsack-problem tag here.
精彩评论