C# - Zahlen in Gruppen mit gleicher Summe sortieren

Veröffentlicht von Koopakiller am 8/9/2014

(0 Bewertungen)

Angenommen man verlegt Rohrleitungen und braucht mehrere, verschiedene Längen und hat mehrere Rohre gleicher Länge zur Verfügung.

Diese Methode kann eine Liste von Double Werten so verteilen, dass die Rohrlängen möglichst Effektiv verwendet werden können.

Ein anderes einsatzbeispiel ist das Auffüllen von Verpackungen aus verschiedenen Teilmengen.

Benötigte Namespaces
System.Collections.Generic
System.Linq
Für das Beispiel:
System

Beispielanwendung

//var lst = new List<double>(new double[] { 1, 1, 1, 2, 2, 3, 4, 4, 5, 8, 13, 21, 34 });
var lst = new List<double>(new double[] { 1, 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 });
Console.WriteLine("Given:");
Console.WriteLine(string.Join(", ", lst));
Console.WriteLine();

//Beispiel: Es sollen exakt 30 Tabletten in die Dose aus verschiedenen Teilmengen gepackt werden.
Console.WriteLine("Exact");
var x1 = lst.Combine(20, CombineMode.Exact).ToList();
Output(lst, x1);

//Beispiel: Es sollen bestimmte Rohrlängen aus festen Längen geschnitten werden.
Console.WriteLine("LessOrExact");
var x2 = lst.Combine(20, CombineMode.LessOrExact).ToList();
Output(lst, x2);

//Beispiel: Es sollen mindestens 500g aus mehreren Teilgewichten abgepackt werden.
Console.WriteLine("MoreOrExact");
var x3 = lst.Combine(20, CombineMode.MoreOrExact).ToList();
Output(lst, x3);

Console.ReadKey();

public static class Extensions
{
    /// <summary>
    /// Versucht die Elemente einer Sequenz in Abschnitte gleicher Größe einzuordnen.
    /// </summary>
    /// <param name="source">Die Quellliste.</param>
    /// <param name="expected">Die Länge (Summe) einer Teilliste.</param>
    /// <param name="mode">Der Modus, wie die Methode Abweichungen behandeln soll.</param>
    /// <returns>Eine Liste mit möglichen Kombinationen von <paramref name="source"/>. Die inneren Listen enthalten die Indíces auf Elemente von <paramref name="source"/>.</returns>
    public static IEnumerable<List<int>> Combine(this List<double> source, double expected, CombineMode mode)
    {
        var flags = Enumerable.Repeat(true, source.Count).ToArray();
        source.Sort();
        List<double> lst;
        List<int> indexes;

        do
        {
            lst = new List<double>();
            indexes = new List<int>();
            double crnt = expected;
            for (int i = source.Count - 1; i >= 0 && crnt > 0; --i)
            {
                if (flags[i] && source[i] <= crnt)
                {
                    crnt -= source[i];
                    flags[i] = false;
                    indexes.Add(i);
                }
            }
            switch (mode)
            {
                case CombineMode.Exact:
                    if (crnt == 0)
                        yield return indexes;
                    else
                        yield break;
                    break;
                case CombineMode.LessOrExact:
                    yield return indexes;
                    break;
                case CombineMode.MoreOrExact:
                    if (crnt != 0 && source.Count > 0)
                    {
                        for (int i = 0; i < source.Count; ++i)
                        {
                            if (flags[i])
                            {
                                flags[i] = false;
                                indexes.Add(i);
                                break;
                            }
                        }
                    }
                    yield return indexes;
                    break;
            }
        } while (indexes.Count != 0);
    }

}
/// <summary>
/// Stellt die verfügbaren Modi für die <see cref="Extensions.Combine"/>-Methode dar. 
/// </summary>
public enum CombineMode
{
    /// <summary>
    /// Die Summe der Elemente muss mit dem übergebenen Wert übereinstimmen oder weniger sein.
    /// </summary>
    LessOrExact,
    /// <summary>
    /// Die Summe der Elemente muss mit dem übergebenen Wert übereinstimmen oder größer sein.
    /// </summary>
    MoreOrExact,
    /// <summary>
    /// Die Summe der Elemente muss mit dem übergebenen Wert übereinstimmen.
    /// </summary>
    Exact,
}

Abgelegt unter Sortieren, Sort, List, Extension.

Kommentare zum Snippet

Logge dich ein, um hier zu kommentieren!

C# - Zahlen in Gruppen mit gleicher Summe sortieren

Kommentare zum Snippet

Ähnliche Snippets

Suche

Letzte Kommentare