AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteilen
Thema durchsuchen
Ansicht
Themen-Optionen

Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteilen

Ein Thema von Kostas · begonnen am 24. Dez 2009 · letzter Beitrag vom 24. Dez 2009
Antwort Antwort
Kostas

Registriert seit: 14. Mai 2003
Ort: Gerstrhofen
1.099 Beiträge
 
Delphi 10 Seattle Enterprise
 
#1

Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteilen

  Alt 24. Dez 2009, 00:35
Hallo zusammen,

ich habe genau 84 Werte zwischen 180.0 und 185.0 z.B.:182.8, 183.4, 183.9, 183.2 u.s.w.
Die Werte sollen aufgeteilt werden in sechs Listen je 14 Werte 14x6=84 Werte.
Dabei soll die Summe jeder einzelnen Liste nachezu den gleichen Summen-Wert ergeben.

Hat jemand eine Idee wie man das machen könnte.

Gruß Kostas
  Mit Zitat antworten Zitat
Torpedo

Registriert seit: 21. Dez 2003
410 Beiträge
 
#2

Re: Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteil

  Alt 24. Dez 2009, 01:15
Das ist wahrscheinlich kein Sortierproblem, sondern ein Optimierungsproblem.
Man könnte zuerst die Summe aller Elemente bilden und diese durch 6 teilen. Dann weiß man, welche Summe jede Liste haben soll.
Den Rest könnte man mit Bei Google suchenBacktracking lösen.
  Mit Zitat antworten Zitat
Kostas

Registriert seit: 14. Mai 2003
Ort: Gerstrhofen
1.099 Beiträge
 
Delphi 10 Seattle Enterprise
 
#3

Re: Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteil

  Alt 24. Dez 2009, 01:22
Zitat von Torpedo:
Das ist wahrscheinlich kein Sortierproblem, sondern ein Optimierungsproblem.
Man könnte zuerst die Summe aller Elemente bilden und diese durch 6 teilen. Dann weiß man, welche Summe jede Liste haben soll.
Den Rest könnte man mit Bei Google suchenBacktracking lösen.
Danke für den Hinweis. Ich werde mir das Prinzip Backtracking mal anschauen das könnte interessant sein.
Dankeschön.

Gruß Kostas
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#4

Re: Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteil

  Alt 24. Dez 2009, 02:14
Man könnte es auch so lösen:
Die Zahlen werden anfangs der Reihe nach auf die 6 Listen verteilt.
Genauso wie man Karten an Pokerspieler ausgeben würde.

Dann wird die Summe jeder Liste gebildet und die Liste mit der grössten und der kleinsten Summe herausgegriffen.
Man berechnet den Durchschnitt (Summe / 14.0) und sucht nun in der Liste mit der grössten Summe eine Zahl, die grösser als dieser Durchschnitt ist.
In der Liste mit der kleinsten Summe sucht man eine Zahl, die kleiner als der Durchschnitt dieser Liste ist.
Die beiden gefundenen Zahlen werden einfach vertauscht.
Wenn man dieses Spielchen so ungefähr 50 bis 500 Mal wiederholt, sollten sich die Summen auf magische Weise angenähert haben.
fork me on Github
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.686 Beiträge
 
Delphi 2007 Enterprise
 
#5

Re: Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteil

  Alt 24. Dez 2009, 02:21
Ein recht naiver Ansatz, der jedoch nicht immer zur optimalen Lösung führt, wäre einfach so zu beginnen wie sx2008 schrieb: Erst in jede Liste ein Wert. Die Liste, die die kleinste Summe hat, bekommt den nächsten Wert, und das so lange bis alles verteilt ist.

Ein möglicher Schritt um das zu optimieren wäre noch, die Ausgangsliste vor ab absteigend zu sortieren. So dass zuerst alle größten Werte verteilt werden, und zum Ende die kleineren kommen, welche dann keine brachialen Unterschiede ("Summensprünge") verusachen.
Das macht es zwar besser, aber die wirklich optimale Lösung wird man nur via Backtracking erhalten können wenn ich das richtig sehe. Das Problem scheint mir NP-vollständig zu sein.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#6

Re: Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteil

  Alt 24. Dez 2009, 08:58
Wenn man das auf eine Liste reduziert, sieht das fatal nach dem Knapsack-Problem aus.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#7

Re: Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteil

  Alt 24. Dez 2009, 09:27
Hallo,

eventuell hilft ja auch das:

Zuerst alle Werte in eine temporäre Liste und diese sortieren.
Nun in die erste Liste den größten und den kleinsten Wert und diese aus der temporären Liste entfernen.
In die zweite Liste wiederum den größten und den kleinsten Wert und diese aus der temporären Liste entfernen.
In die dritte Liste wiederum den ...
In die vierte Liste wiederum ...
In die fünfte Liste ...
In die sechste ...
und wieder von vorne ... bis die temporäre Liste leer ist.
Je nach Verteilung der 84 Ursprungswerten könnte dies zumindest relativ nah an das gewünschte Ergebnis kommen.

Eventuell nach der Verteilung noch die Summe je Liste bilden und dann Einzelwerte zwischen den Listen tauschen, um die Summen anzunähern. Wenn ich das richtig sehe, liegt die durchschnittliche Differenz zwischen den Werten ja nur bei ca. 0,06. [OPTIMISMUS ON]Da dürfte diese Methode doch relativ nah beieinanderliegende Ergebnisse liefern.[OPTIMISMUS OFF]

Das erinnert mich ein bisserl an die Methode "PI erschießen", hierzu gibt es unter http://www.unixboard.de/vb3/showthread.php?t=12105 eine Methode in Java (am Ende der Seite - siehe auch Monte-Carlo-Algorithmus).
  Mit Zitat antworten Zitat
Antwort Antwort


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 03:07 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz