Mögl. Ziehungen o. Z. aus 1..n, sodass summe <=k
Neue Frage »

04.07.2008, 14:59 DeGT Auf diesen Beitrag antworten »
Mögl. Ziehungen o. Z. aus 1..n, sodass summe <=k
Hallo ihr,

ich habe folgendes Problem: Für ein Projekt an der Uni brauchen wir eine nette Formel, die uns ausrechnet, wie viele Möglichkeiten es gibt, aus den Zahlen 1-n ohne Zurücklegen Zahlen zu ziehen, sodass ihre Summe kleiner-gleich (oder gleich ) k ist.

Es sieht zwar so aus, dass wir das Problem mit "gleich k" mit einer Normalverteilung annähern können (wobei uns allerdings noch die Parameter fehlen), aber Beweis durch Intuition ist nichts, was wir anstreben. ;-)

Da ich "nur" Informatik studiere, wurde das Problem erstmal konstruktiv gelöst, was aber 1. nicht skaliert und 2. nicht so befriedigend ist.
04.07.2008, 15:08 AD Auf diesen Beitrag antworten »

Die Anzahl der Summanden ist wohl frei, also nicht festgelegt?
04.07.2008, 15:40 DeGT Auf diesen Beitrag antworten »

In meiner jetzigen Lösung ist es nicht egal, mein Fehler.

Es geht hier um die Wahrscheinlichkeit, dass man eine Liste mit Bubblesort mit x Vertauschungen sortieren kann.
Wir wollen das für ein Gütemaß für Textrelevanzsortierer benutzen.


Die Idee ist folgendermaßen:
Gegeben ist eine Liste mit n Elementen a und n Elementen b. Diese teilen wir in der Mitte und nummerieren von dieser aus (einmal ab 0 und einmal ab 1):
code: 
1:
2:
3:
4:

 ab  ab
 10  12

Die Summe der nötigen Vertauschungen ist genau die Summe der Werte der in der falschen Hälfte liegenden Elemente. In diesem Fall 0+1=1.

Die Anzahl der Möglichen Listen, die sich mit maxvalue Vertauschungen sortieren lassen, habe ich dann über folgenden Code ermittelt:
code: 
1:
2:
3:
4:
5:
6:
7:
8:

    for value in xrange(maxvalue, 0, -1):
        for draws in xrange(num_elements, 0, -1):
            # all possibilities to split value into two parts
            for j in xrange(1, value+1):
                result += possibilities(num_elements, draws, j) * \
                    possibilities(num_elements, draws, value-j+draws)

das "+draws" ist hierbei ein Hack, um die das Ziehen von Null an zu simulieren.

Als Formel sieht das ganze so aus:


possibilities gibt die Anzahl der Möglichkeiten, aus n Elementen mit d Ziehungen auf genau den Wert Value zu kommen. Zumindest diese Funktion sollte nicht mehr durch Konstruktion aller dieser Listen gelöst werden.
04.07.2008, 15:44 AD Auf diesen Beitrag antworten »

Erst kürzlich war eine verwandte Anfrage hier aufgeschlagen:

abgebrochenes Bubble-Sort

Da war aber nicht die Anzahl der Vertauschungen, sondern die Anzahl der Bubblesort-Durchläufe (mit egal wieviel Vertauschungen pro Durchlauf) das Hauptaugenmerk.
04.07.2008, 16:36 DeGT Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Erst kürzlich war eine verwandte Anfrage hier aufgeschlagen:

abgebrochenes Bubble-Sort

Da war aber nicht die Anzahl der Vertauschungen, sondern die Anzahl der Bubblesort-Durchläufe (mit egal wieviel Vertauschungen pro Durchlauf) das Hauptaugenmerk.

Ich sehe im Moment nicht, wie ich die dortigen Lösungen auf das hiesige Problem anwenden kann.
04.07.2008, 16:38 AD Auf diesen Beitrag antworten »

Ich auch nicht.

Aber eine Anmerkung zur Verwandtheit des Problems darf doch trotzdem erlaubt sein, oder? Augenzwinkern
 Anzeige 
 
04.07.2008, 16:42 DeGT Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Ich auch nicht.

Aber eine Anmerkung zur Verwandtheit des Problems darf doch trotzdem erlaubt sein, oder? Augenzwinkern

Ja, auf jeden Fall.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Stochastik & Kombinatorik » Mögl. Ziehungen o. Z. aus 1..n, sodass summe <=k