|
Hi,
I am looking for the best way to sort multiple lists of unique items so none of the list items match at the same index.
Here is an example of what I want to do.
Original lists:
List 1: A, B, E, F
List 2: A, C, D, E
List 3: A, C, E, F
List 4: A, D, F, G
Should be sorted to:
List 1: A, B, E, F
List 2: C, A, D, E
List 3: E, F, A, C
List 4: D, G, F, A
Can anyone see a good way to solve this? Let me know if the above doesn't make sense.
Thanks
J
|
|
|
|
|
If the elements of the list can be completely random, then it seems to me you'd have to do this brute-force style. I don't see an obvious algorithm for speeding this up.
I do know that genetic algorithms are used to generate Sudoku tables (which is a similar problem to the above), but GA's are rather non-trivial to implement. It's probably easier to brute-force it for small lists.
|
|
|
|
|
Thanks, yeah I was thinking that I might need to do something pretty ugly to get this working. I've potentially got 5 sets of 42 items to sort so it could turn into alot of cycles to get 5 unique sets.
J
|
|
|
|
|
jrg2000 wrote: I've potentially got 5 sets of 42 items to sort
As a matter of interest, how many different items can there be in each set of 42 and do you have repeats? e.g. the sets are collections of different elements from a set of 80 elements, with no repeats OR the sets are collections from 10 elements with arbitrary numbers of repeats.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I think this is really a form of a timetable problem, for which there are a number of references and algorithms on the web. Genetic algorithms are one common approach.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Thanks I didn't think of timetables but that is exactly what I am trying to do. I'll definately look into that.
J
|
|
|
|
|
I would assume the best way, is the following.
1. Assume the first list will not be sorted.
2. Move down the first list, verifying that each subsequent list doesn't have the matching item.
3. If an item matches in that list with the current item in the first list, push it to the end.
4. Iterate till the end.
5. Once at the end, you look over the last items, if any match the final element of the first list, then you must swap that item with one of the items in the list that doesn't conflict with the first list's item.
Basically, once you're at the end, you're down to a single lookup for each list. That should be as simple as you can get it.
Does that make sense?
|
|
|
|
|
Andrew Rissing wrote: I would assume the best way, is the following.
This is a way, it may not be the best way. The reason is that it there is no guarantee that it will work. When you find a clash you make a decision as to what swap to make to resolve it. There are probably many ways to resolve each clash - you choose one. If you make the wrong choice your algorithm may get stuck (i.e you end up with a clash that you cannot resolve - all the elements you have left to swap with clash as well) - there is no way of backtracking in your algorithm to change those earlier choices. If you include backtracking to try all the choices you can make - then you have a simple exhaustive search.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Ah, this should be easy.
Assume you have list1 fully filled.
list2 = new list<char>();
for (int i = 1; i < list1.size(); i++)
{
list2.push_back(list1.at(i));
}
list2.push_back(list1.at(0);
</char>
Basically, you're shifting indices by one, and keep doing it for every index. The theoretical maximum number of lists you can make is the size of the initial list, since you can only shift indices that much before they repeat again (informal proof). I can demonstrate this more formally, but I won't write it here.
|
|
|
|
|
hi!
i have a question. that is we have ha a problem "which one is smaller n pow 2, 1000 pow n, n pow n, n pow 1000 , when n value is nearer to infinite" plz also give reason along with answer
Best Regards,
Huma Satti
|
|
|
|
|
Exponential functions are larger then powers of a number when n is nearer infinity
Giorgi Dalakishvili
#region signature
my articles
#endregion
|
|
|
|
|
 He's not comparing exponential functions.
|
|
|
|
|
|
Try looking at the logarithms of these values and comparing them. You should easily see the answer.
|
|
|
|
|
THNX ALOT 4 UR HELP SO NICE OV U
|
|
|
|
|
I assume you mean the derivatives? Once upon a time I learned about something that I recall as l'Hôpital's rule[^]. On the other hand, I have no clue what the hell the derivation of n log n is.  Do you think Ilidiot knows? 
--
Kein Mitleid Für Die Mehrheit
|
|
|
|
|
My guess is
n pow 2
your task is to proof it (by induction?)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
SO NICE OV U THNX ALOT OV UR HELP
|
|
|
|
|
huma satti wrote: when n value is nearer to infinite
Is n interger? real number? complex number? What interval are we talking about? Positive or negative infinity? I'd give it back to teacher and say that (s)he formulated the problem too vaguely :P
[ My Blog] "Visual studio desperately needs some performance improvements. It is sometimes almost as slow as eclipse." - Rüdiger Klaehn "Real men use mspaint for writing code and notepad for designing graphics." - Anna-Jayne Metcalfe
|
|
|
|
|
huma satti wrote: when n value is nearer to infinite
(just for the sake of argumentation, I'm pretty certain there are some mathematical proof of each ...)
Does it really make a difference when n is near infinity ? the results will be infinity anyway.
|
|
|
|
|
Maximilien wrote: Does it really make a difference when n is near infinity ? the results will be infinity anyway.
I think the question is about the asymptotic properties of the various quantities. In a practical sense the exercise is useful for comparing orders of algorithms. Aside from that, if n is infinity then you can't compare them, no. "Close to infinity" just means "very large but not infinity".
|
|
|
|
|
Hi,
I have a laplace function:
<br />
30/(3+s)^2<br />
I am trying to find the inverse of it.
I know the answer from (MATLAB) is
<br />
30*exp(-3*t)*t<br />
Could anyone lend a hand on getting from A to B on this one?
I know that to get the answer above, the original equation must be re-arranged to be:
<br />
30/(s+3)*(1/s^2) <- this is wrong :-(.<br />
<br />
where:<br />
<br />
30/(s+3) transforms to 30*exp(-3*t)<br />
(1/s^2) transforms to t<br />
Any help would be appreciated.
Cheers,
modified on Sunday, May 4, 2008 3:11 AM
|
|
|
|
|
Isn't this just the nth power with frequency shift transform?
i.e: 1/(s+a)^(n+1)
In this case, a=3 and n = 1
the transform is t^n/n! * exp(-at) so with a = 3 and n = 1:
t^1/1! * exp(-3t)
=texp(-3t)
Since 30 is a constant it doesn't affect the transform and we just put it back in:
30*t*exp(-3t)
This is just an application of the shifting theorem:
For an arbitrary constant a > 0
L{exp(-at)f(t)} = F(s+a)
|
|
|
|
|
Yea it was the 1st shifting theorom. (like you said above).
Cheers,
|
|
|
|
|
Meh, Freud would laugh at me..
I read "Need help inverting a LAPDANCE function"
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
