开发者

Find tracks that match group by length

开发者 https://www.devze.com 2023-02-26 05:20 出处:网络
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):

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.

0

精彩评论

暂无评论...
验证码 换一张
取 消