Partitionen einer Zahl

volkard

Wäre das rekursiv nicht viel einfacher?

wie meinst du, könntest du mir zeigen wie?

volkard

Fortuner schrieb:

wie meinst du, könntest du mir zeigen wie?

War doch nicht einfach. Und ist leider in C++.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void part(vector<int>& ergebnis,int rest,int obergrenze){
//als Beispielzahlen nehme ich die Partitionierungen von 4. 
//vector<int> entspricht wohl System.Collections.Generic.List<int>
    if(rest==0){//Wein kein Rest mehjr zu verteilen ist
        for(size_t i=0;i<ergebnis.size();++i)//Liste ausgeben
            cout<<ergebnis[i]<<' ';
        cout<<'\n';
        return;//und fertig, es ist ja kein zu verteilender Rest mehr da. 
    }

    for(int i=rest;i!=0;--i){//die erste zahl kann von 4 bis 1 sein
        ergebnis.push_back(i);//Und die wird hinten an die Liste angefügt
        if(i<=obergrenze)//Ist nur dazu da, soprtierte Ausgabe zu erzwingen, 
//alles Unsortierte wird verworfen
            part(ergebnis,rest-i,min(obergrenze,i));//Und rest-i ist der neue Rest
        ergebnis.pop_back();//i wieder wegmache4n für den nächsten Durchlauf. 
    }
}

int main() {
    vector<int> speicher;
    part(speicher,4,4);
}

Bashar

Mal schnell was zusammengehackt, sicher nicht besonders schön:

static IEnumerable<int[]> Partitions(int n, int m, List<int> head)
        {
            int min = System.Math.Min(n, m);
            for (int i = 1; i <= min; ++i)
            {
                List<int> newHead = new List<int>(head);
                newHead.Add(i);
                if (n == i)
                    yield return newHead.ToArray();
                else
                    foreach (int[] p in Partitions(n - i, i, newHead))
                        yield return p;
            }
        }

        static IEnumerable<int[]> Partitions(int n)
        {
            return Partitions(n, n, new List<int>());
        }

Das soll der ganze code sein ? bisschen kurz oder?

Bashar schrieb:

Mal schnell was zusammengehackt, sicher nicht besonders schön:

static IEnumerable<int[]> Partitions(int n, int m, List<int> head)
        {
            int min = System.Math.Min(n, m);
            for (int i = 1; i <= min; ++i)
            {
                List<int> newHead = new List<int>(head);
                newHead.Add(i);
                if (n == i)
                    yield return newHead.ToArray();
                else
                    foreach (int[] p in Partitions(n - i, i, newHead))
                        yield return p;
            }
        }

        static IEnumerable<int[]> Partitions(int n)
        {
            return Partitions(n, n, new List<int>());
        }

Bashar

Das ist alles wichtige.

Es kann höchstens sein, dass das noch ein bisschen zu lang bzw. unelegant ist. Ich hab zuerst was gebastelt, was die geordneten Partitionen zurückgibt. Es sind aber anscheinend die ungeordneten Partitionen gesucht, d.h. dass die Reihenfolge der Summanden keine Rolle spielt und somit 1+2 und 2+1 die gleiche Partition von 3 darstellen. Also hab ich den Code modifiziert und nicht nochmal von vorne gedacht. Kann durchaus sein, dass es besser geht.

freaky

fortuner schrieb:

Das soll der ganze code sein ? bisschen kurz oder?

Hast du den Code denn mal getestet? Nur weil der Code kürzer als deiner ist, heißt es nicht, dass er falsch ist.

EXDW

Der Code von Bashar funktioniert:

[TestClass]
public class PartitionsSolverTest
{
	[TestMethod]
	public void Partitions_4_ReturnsValidPossibilities()
	{
		Assert.IsTrue(Test(4, 5));
	}

	[TestMethod]
	public void Partitions_13_ReturnsValidPossibilities()
	{
		Assert.IsTrue(Test(13, 101));
	}

	[TestMethod]
	public void Partitions_45_ReturnsValidPossibilities()
	{
		Assert.IsTrue(Test(45, 89134));
	}

	private bool Test(int no, int count)
	{
		var solver = new PartitionsSolver();
		var possibilities = solver.Partitions(no);
		foreach (var possibility in possibilities)
			if (possibility.Sum() != no)
				return false;
		return possibilities.Count() == count;
	}
}

Alles Grün.

//Edit: Tests angepasst nach Volkards Liste

volkard

David W schrieb:

nur ob die richtige Anzahl von Möglichkeiten ermittelt wird habe ich gerade nicht getestet):

Das http://oeis.org/A000041 sollten die richtigen Anzahlen sein, vermute ich.

EXDW

Hab die Tests angepasst - thx.