Register | Sign In


Understanding through Discussion


EvC Forum active members: 65 (9162 total)
4 online now:
Newest Member: popoi
Post Volume: Total: 915,808 Year: 3,065/9,624 Month: 910/1,588 Week: 93/223 Day: 4/17 Hour: 1/1


Thread  Details

Email This Thread
Newer Topic | Older Topic
  
Author Topic:   sorting problem
matheo
Inactive Junior Member


Message 1 of 11 (72242)
12-11-2003 2:25 AM


hello,
im having trouble to resolve this problem. maybe someone of you knows a solution.
I have a music collection composed of artists and songs.
I want to listen to each song but each songs should be spread out evently so the same artist is not played twice in a row. example: if artist-1 has 10 songs and the total songs are 100, then 1 song of every 10 would be of artist-1. the order the artists are played doesnt matter.
whats the formula to achive this?
My collection: (12 songs total)
A1 (5 songs): S1,S2,S3,S4,S5
A2 (3 songs): S1,S2,S3
A3 (3 songs): S1,S2,S3
A4 (1 songs): S1
Possible result:
A1-S1
A2-S1
A1-S2
A2-S2
A1-S3
A2-S3
A1-S4
A3-S1
A1-S5
A3-S2
A4-S1
A3-S3
thanks in advance

Replies to this message:
 Message 2 by Percy, posted 12-11-2003 7:27 AM matheo has not replied
 Message 3 by Rei, posted 12-11-2003 1:37 PM matheo has not replied
 Message 5 by Rrhain, posted 12-12-2003 4:01 AM matheo has not replied
 Message 6 by Peter, posted 12-22-2003 7:34 AM matheo has not replied

  
Percy
Member
Posts: 22389
From: New Hampshire
Joined: 12-23-2000
Member Rating: 5.2


Message 2 of 11 (72257)
12-11-2003 7:27 AM
Reply to: Message 1 by matheo
12-11-2003 2:25 AM


Hi Matheo!
Just making sure I understand the problem.
whats the formula to achive this?
You already described the formula, so I'm guessing that you're asking how can you automatically produce a list because you don't actually have four artists and 12 songs total, but many artists and hundreds of songs total, and producing a randomized list by hand is just too tedious.
Is your music on your computer or somewhere else? If it's on your computer then my guess is that there are many programs out there that include a randomized playlist feature. Some programs are probably better than others, so some may make sure that the same artist doesn't have consecutive songs, and some may not.
--Percy

This message is a reply to:
 Message 1 by matheo, posted 12-11-2003 2:25 AM matheo has not replied

  
Rei
Member (Idle past 7012 days)
Posts: 1546
From: Iowa City, IA
Joined: 09-03-2003


Message 3 of 11 (72303)
12-11-2003 1:37 PM
Reply to: Message 1 by matheo
12-11-2003 2:25 AM


Here's a suggestion:
Take all of the CDs of the different songs that you have. Place them in a big tub of water, and stir violently, then drain the water. As we all know, floods sort things nice and perfectly without regard to size, shape, and habitat, but only to one thing: How you need them to be sorted.
The bigger and more violent the flood, the better it does this, so fill that tub full and stir hard!
------------------
"Illuminant light,
illuminate me."

This message is a reply to:
 Message 1 by matheo, posted 12-11-2003 2:25 AM matheo has not replied

Replies to this message:
 Message 4 by Loudmouth, posted 12-11-2003 2:53 PM Rei has not replied

  
Loudmouth
Inactive Member


Message 4 of 11 (72318)
12-11-2003 2:53 PM
Reply to: Message 3 by Rei
12-11-2003 1:37 PM


I think I just pissed my pants I laughed so hard. Maybe the CD's will separate out by publish date, or the songs with the fastest beat will make it to the top of the pile. Hehe, great post Rei.

This message is a reply to:
 Message 3 by Rei, posted 12-11-2003 1:37 PM Rei has not replied

Replies to this message:
 Message 8 by Abshalom, posted 12-22-2003 6:13 PM Loudmouth has not replied

  
Rrhain
Member
Posts: 6351
From: San Diego, CA, USA
Joined: 05-03-2003


Message 5 of 11 (72468)
12-12-2003 4:01 AM
Reply to: Message 1 by matheo
12-11-2003 2:25 AM


Sounds like somebody is in an Algorithms class and has a final exam coming up.
You haven't even touched upon the possibility that some starting points are unsolvable. For example, if you have 100 songs but only two artists, one of which has made 75 of them and the other has made 25, then there is no way to sort them the way you want.
How might one determine if the problem has a solution at all? No, I'm not going to tell you how to do it...you have to do your own homework.
Once you have that down, you might be inspired about how to design an algorithm that would generate a list. Notice the size of the set of songs for each individual artist. How would one interleave one set into the others? Here's a hint: Think of a checkerboard.
This will certainly give you a possible sorting, but it won't give you all possible sortings. Off the top of my head, I can't think of a single algorithm that would generate all possible sortings, but that doesn't mean one doesn't exist.
------------------
Rrhain
WWJD? JWRTFM!

This message is a reply to:
 Message 1 by matheo, posted 12-11-2003 2:25 AM matheo has not replied

Replies to this message:
 Message 7 by Rrhain, posted 12-22-2003 12:59 PM Rrhain has not replied

  
Peter
Member (Idle past 1478 days)
Posts: 2161
From: Cambridgeshire, UK.
Joined: 02-05-2002


Message 6 of 11 (74649)
12-22-2003 7:34 AM
Reply to: Message 1 by matheo
12-11-2003 2:25 AM


Compile two lists of equal length (leaving the
tracks in order i.e. the lists are concatinations).
Then make a complete list by removing the head of
each list alternately to a new list.
If you cannot make two equi-sized lists without splitting
a CD you cannot gaurantee a solution to the problem
(assuming each CD has a different artist, otherwise you
first have to make by-artist lists).

This message is a reply to:
 Message 1 by matheo, posted 12-11-2003 2:25 AM matheo has not replied

  
Rrhain
Member
Posts: 6351
From: San Diego, CA, USA
Joined: 05-03-2003


Message 7 of 11 (74676)
12-22-2003 12:59 PM
Reply to: Message 5 by Rrhain
12-12-2003 4:01 AM


Here's the algorithm I had in mind:
First, if the total number of songs is even, no one artist can have more than half of the songs. If the total number of songs is odd, then no one artist can have more than one-half-plus-one of the songs. This is because is if all you have is one other artist, you're going to do an every-other solution and you need to have enough of the other artist to fit between all the original artist's entries.
Now, imagine a gigantic chessboard with as many squares as you need in both directions. Going down the left-hand column, enter the titles for the artist that has the most songs on the squares. Thus, the last song of the most common artist is on the nth square of the leftmost column.
Now, go back to the top, but move one column over. Take the next most numerous artist and start entering its entries on the squares going down the second column. If you run out of entries before reaching the nth square in the second column, take the next most numerous artist and keep going until you reach the nth square of the second column. At that point, go back to the top and continue entering down the third column.
Keep doing this until you run out of songs to enter. To get your sorted list, simply start at the very first square (uppermost left) and read across the rows.
We know this will work because the most numerous artist has, at most half-plus-one songs. Thus, the second column has at most n items, none of which are the first artist and at least n-1 items, meaning that every row has at least two entries except the very last one and thus the final transversal will always have at least one entry that isn't the first artist before wrapping around.
This recurses for all the other columns. Even though we may "wrap around" the bottom of one column to start at the top of the next, we will never catch up to have two entries by the same artist side-by-side horizontally because each artist has fewer than n songs and the column length is n.
And since there is guaranteed a second column and no row has the same artist side-by-side, transversing the grid horizontally will guarantee that you never hit the same artist twice in a row.
Now, there is an improvement one could make to this algorithm if one were programming it. Does it really matter that other than the choice of the most numerous artist for the first column that we choose the rest of the artists in descending order of size? No. Since all of the remaining artists are no larger than the most numerous, we can put them into the grid in any order once we have chosen the most numerous in order to set the column size to that cardinality. We never have to worry about overlap from column to column.
------------------
Rrhain
WWJD? JWRTFM!

This message is a reply to:
 Message 5 by Rrhain, posted 12-12-2003 4:01 AM Rrhain has not replied

Replies to this message:
 Message 10 by Peter, posted 12-23-2003 4:29 AM Rrhain has not replied

  
Abshalom
Inactive Member


Message 8 of 11 (74703)
12-22-2003 6:13 PM
Reply to: Message 4 by Loudmouth
12-11-2003 2:53 PM


Floaters
Loud: I'll bet a dollar to a donut that the gangster rap will float for obvious reasons of content.

This message is a reply to:
 Message 4 by Loudmouth, posted 12-11-2003 2:53 PM Loudmouth has not replied

Replies to this message:
 Message 9 by crashfrog, posted 12-22-2003 7:34 PM Abshalom has not replied

  
crashfrog
Member (Idle past 1466 days)
Posts: 19762
From: Silver Spring, MD
Joined: 03-20-2003


Message 9 of 11 (74716)
12-22-2003 7:34 PM
Reply to: Message 8 by Abshalom
12-22-2003 6:13 PM


I'll bet a dollar to a donut that the gangster rap will float for obvious reasons of content.
To quote House of Pain in "Jump Around":
quote:
I'm the cream of the crop / I rise to the top

This message is a reply to:
 Message 8 by Abshalom, posted 12-22-2003 6:13 PM Abshalom has not replied

Replies to this message:
 Message 11 by Peter, posted 01-09-2004 5:11 AM crashfrog has not replied

  
Peter
Member (Idle past 1478 days)
Posts: 2161
From: Cambridgeshire, UK.
Joined: 02-05-2002


Message 10 of 11 (74808)
12-23-2003 4:29 AM
Reply to: Message 7 by Rrhain
12-22-2003 12:59 PM


My way produces the list given as an example
solution, but I think I prefer your approach
because it is less sensitive to CD lengths (in
tracks).

This message is a reply to:
 Message 7 by Rrhain, posted 12-22-2003 12:59 PM Rrhain has not replied

  
Peter
Member (Idle past 1478 days)
Posts: 2161
From: Cambridgeshire, UK.
Joined: 02-05-2002


Message 11 of 11 (77290)
01-09-2004 5:11 AM
Reply to: Message 9 by crashfrog
12-22-2003 7:34 PM


To quote the Duke of Wellington 'So does the scum.'

This message is a reply to:
 Message 9 by crashfrog, posted 12-22-2003 7:34 PM crashfrog has not replied

  
Newer Topic | Older Topic
Jump to:


Copyright 2001-2023 by EvC Forum, All Rights Reserved

™ Version 4.2
Innovative software from Qwixotic © 2024