Как рассчитать суммирование произвольного набора чисел и всех подмножеств этих чисел?

Question

Скажите, что у меня есть набор чисел:

Group1 = 10, Group2 = 15, Group3 = 20, Group4 = 30

Я хочу вывести суммирование всех подмножеств чисел

10 + 15 = 25
10 + 15 + 20 = 45
10 + 15 + 20 + 30 = 75
15 + 20 = 35
15 + 20 + 30 = 65
20 + 30 = 50
10 + 20 = 30
10 + 30 = 40
10 + 20 + 30 = 60
... (assumed the rest is typed out)

У каждой из этих групп будет имя, поэтому я хотел бы распечатать имена, использованные в расчете, перед результатом:

Group1 + Group2 = 25

Как это сделать?

РЕДАКТИРОВАТЬ: для JacobM, который редактировал теги, это НЕ домашнее задание, и он был бы признателен за вопрос, прежде чем начать редактировать его как таковой. На самом деле я нахожусь на сайте клиента, который пытается сбалансировать набор чисел, и результат исходит неправильно. Моя мысль состояла в том, чтобы определить, какая группа чисел равна дельте между двумя наборами, и это определило бы проблему напрямую.

Примечание: это будут значения с плавающей запятой, а не целые числа.

EDIT2: добавлено произвольно, так что понятно, что я не могу просто набрать это один раз с кучей string.format's .. Я мог бы легко использовать Excel на этом этапе.

Answer 1

Моя мысль состояла в том, чтобы определить, какая группа чисел равна дельте между двумя наборами, и это напрямую определило бы проблему.

Проблема " с учетомцелое число s и набор целых чисел, является ли любое непустое подмножество из установленной суммы в s?"известным как" проблема суммы подмножеств".Это чрезвычайно хорошо изучено, и это NP-Complete.(См. эту ссылку для получения информации о связанной проблеме.)

То есть, это одна из самых сложных проблем, которую необходимо решить за разумное время.Широко распространено мнение (хотя в настоящее время не доказано ), что для этой задачи не может существовать никакого алгоритма за полиномиальное время.Лучшее, что вы можете сделать, это что-то вроде O (2 ^ n) для набора, содержащего n элементов.

(Замечу, что ваша проблема в числах с плавающей точкой, а не в целых числах. Это на самом деле не имеет значения, если вы правильно обрабатываете сравнение рассчитанной суммы с целевой суммой для обработки любой ошибки округления, которая может иметьНакапливается при суммировании.)

Для небольшого количества элементов - вы говорите, что в наборе их всего 15 или около того - лучше всего просто попробовать их все исчерпывающе.Вот как вы это делаете.

Хитрость заключается в том, чтобы понять, что существует одно подмножество для каждого целого числа от 0 до 2 ^ n.Если вы посмотрите на эти числа в двоичном виде:

0000
0001
0010
0011
...

каждое соответствует подмножеству.Первый не имеет участников.Второй имеет только группу 1. Третий имеет только группу 2. У четвертого есть группа 1 и группа 2. И т. Д.

Псевдокод достаточно прост:

for each integer i from 1 to 2^n
{
  sum = 0;
  for each integer b from 1 to n
  {
    if the bth bit of i is on then sum = sum + group(b)
  }
  if sum == target then print out i in binary and quit
}
quit with no solution

Очевидно, этоявляется O (n 2 ^ n).Если вы можете найти алгоритм, который всегда работает лучше, чем O (c ^ n), или докажет , что вы не можете найти такой алгоритм, тогда вы станете знаменитыми навсегда.

В статье Википедии есть лучший алгоритм, который дает ответ намного быстрее большинство , но не все времени.Сначала я остановлюсь на наивном алгоритме, так как на его создание у вас уйдет всего несколько минут;если он неприемлемо медленный, перейдите к более быстрому и более сложному алгоритму.

Answer 2

Это соответствует любой возможной комбинации ...

static void Main(string[] args)
{
    Dictionary<string, float> groups = new Dictionary<string, float>();
    groups.Add("Group1", 10);
    groups.Add("Group2", 15);
    groups.Add("Group3", 20);
    groups.Add("Group4", 30);

    for (int i=0; i < groups.Count - 1; i++)
    {
        Iterate(groups, i, 0, "");
    }

    Console.Read();
}

private static void Iterate(Dictionary<string, float> groups, int k, float sum, string s)
{
    KeyValuePair<string, float> g = groups.ElementAt(k);

    if (string.IsNullOrEmpty(s))
    {
        s = g.Key;
    }
    else
    {
        s += " + " + g.Key;
        Console.WriteLine(s + " = " + (sum + g.Value));
    }

    for (int i = k + 1; i < groups.Count; i++)
    {
        Iterate(groups, i, sum + g.Value, s);
    }
}

Answer 3

Как уже говорилось, ключом к вашему решению является получение всех возможных комбинаций!Вы можете поместить что-то вроде этого в класс static , чтобы зарегистрировать его как метод расширения:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int length = -1)
{
    switch (length)
    {
        case -1:
            foreach (var combination in Enumerable.Range(1, elements.Count()).Select(count => elements.Combinations(count)).SelectMany(c => c))
                yield return combination;
            break;
        case 0:
            yield return new T[0];
            break;
        default:
            if (length < -1) throw new ArgumentOutOfRangeException("length");
            foreach (var combination in 
                elements
                .SelectMany((element, index) => 
                    elements
                    .Skip(index + 1)
                    .Combinations(length - 1)
                    .Select(previous => (new[] { element }).Concat(previous))))
                yield return combination;
            break;
    }
}

... и использовать его так:

static void Main(string[] args)
{
    var groups = new[]
                    {
                        new Tuple<string, int>("Group1", 15),
                        new Tuple<string, int>("Group2", 5),
                        new Tuple<string, int>("Group3", 17),
                    };

    foreach (var sum in groups
        .Combinations()
        .Select(x => 
            string.Join(" + ", x.Select(tuple => tuple.Item1)) + 
            " = " + 
            x.Sum(tuple => tuple.Item2)))
    {
        Console.WriteLine(sum);
    }
    Console.ReadLine();
}

Вывод:

Group1 = 15
Group2 = 5
Group3 = 17
Group1 + Group2 = 20
Group1 + Group3 = 32
Group2 + Group3 = 22
Group1 + Group2 + Group3 = 37

Answer 4

Это довольно классическая комбинационная проблема.См. Этот пост для более подробной информации:

Алгоритм возврата всех комбинаций k элементов из n

Эффективно то, что вы хотите сделать, это итерация от N-choose-1 доN-выберите-N и рассчитать суммы каждого подмножества.

Answer 5

Вот мои 10 центов. Он использует понятие, на которое, я думаю, намекал @DK. Вы берете целое число и конвертируете его в двоичное число, представляющее битовую маску групп для добавления. 1 означает добавить его, 0 означает пропустить его. Он в VB, но должен быть легко преобразован в C #.

    '//Create the group of numbers
    Dim Groups As New List(Of Integer)({10, 15, 20, 30})
    '//Find the total number groups (Same as 2^Groups.Count() - 1 but reads better for me)
    Dim MaxCount = Convert.ToInt32(New String("1"c, Groups.Count), 2)

    '//Will hold our string representation of the current bitmask (0011, 1010, etc)
    Dim Bits As String
    '//Will hold our current total
    Dim Total As Integer
    '//Will hold the names of the groups added
    Dim TextPart As List(Of String)
    '//Loop through all possible combination
    For I = 0 To MaxCount
        '//Create our bitmask
        Bits = Convert.ToString(I, 2).PadLeft(Groups.Count, "0")
        '//Make sure we have got at least 2 groups
        If Bits.Count(Function(ch) ch = "1"c) <= 1 Then Continue For
        '//Re-initialize our group array
        TextPart = New List(Of String)
        '//Reset our total
        Total = 0
        '//Loop through each bit
        For C = 0 To Bits.Count - 1
            '//If its a 1, add it
            If Bits(C) = "1"c Then
                Total += Groups(C)
                TextPart.Add("Group" & (C + 1))
            End If
        Next
        '/Output
        Trace.WriteLine(Join(TextPart.ToArray(), " + ") & " = " & Total)
    Next

Выходы:

Group3 + Group4 = 50
Group2 + Group4 = 45
Group2 + Group3 = 35
Group2 + Group3 + Group4 = 65
Group1 + Group4 = 40
Group1 + Group3 = 30
Group1 + Group3 + Group4 = 60
Group1 + Group2 = 25
Group1 + Group2 + Group4 = 55
Group1 + Group2 + Group3 = 45
Group1 + Group2 + Group3 + Group4 = 75

Answer 6

Хорошо, последний был не так прост, как я думал. На самом деле я проверил это на этот раз, и он дает правильные результаты.

void PrintInner( string output, float total, List<KeyValuePair<string, float>> children )
{
    var parent = children[0];
    var innerChildren = new List<KeyValuePair<string, float>>();
    innerChildren.AddRange( children );
    innerChildren.Remove( parent );

    output += parent.Key + ":" + parent.Value.ToString();
    total += parent.Value;

    if( output != "" ) // Will prevent outputting "Group1:10 = 10", comment out if desired.
        Console.WriteLine( output + " = " + total.ToString() );
    output += " + ";

    while( innerChildren.Count > 0 )
    {
        PrintInner( output, total, innerChildren );
        innerChildren.RemoveAt( 0 );
    }

}


void PrintAll()
{
    var items = new List<KeyValuePair<string,float>>()
    {
        new KeyValuePair<string,float>>( "Group1", 10 ),
        new KeyValuePair<string,float>>( "Group2", 15 ),
        new KeyValuePair<string,float>>( "Group3", 20 ),
        new KeyValuePair<string,float>>( "Group4", 30 )
    }

    while( items.Count > 0 )
    {
        PrintInner( "", 0, items );
        items.RemoveAt( 0 );
    }
}

Answer 7

Я задал вопрос о преобразовании целого числа в байтовое представление для решения проблемы, подобной этой.

Преобразование целого числа в битовое представление

Answer 8

Если для группы выбран пользовательский тип данных, вы можете перегрузить +, -, *, /, =, ==, !=, а затем +=, -=, *= и /= операторы, как показано здесь: MSDN: Учебник по перегрузке операторов

Если ваш тип данных является собственным типом данных: int (Int32),long, decimal, double или float вы можете выполнять операции, которые у вас есть.

Чтобы вывести сумму ваших чисел, вы можете использовать:

String.Format("{0} + {1} = {2}", Group1, Group2, (Group1 + Group2));

или

String.Format("{0} + {1} + {2} = {3}", Group1, Group2, Group3, (Group1 + Group2 + Group3));

Наконец, если в этих примерах Group является пользовательским типом данных, вы бытакже необходимо перегрузить метод ToString(), чтобы он мог правильно отображаться.

<bleepzter/>

ОК, часть 2 - Разработка алгоритма OO?

Итак, допустим, у вас есть следующее:

public class Set: List<float>
{
    public Set():base(){}

    public static Set operator+(Set set1, Set set2)
    {
        Set result = new Set();
        result.AddRange(set1.ToArray());
        result.AddRange(set2.ToArray());
        return result;
    }

    public float Sum
    {
        get
        {
            if( this.Count == 0 )
                return 0F;

            return this.Sum();                
        }
    }

    public override string ToString()
    {
        string formatString = string.Empty;
        string result = string.Empty;

        for(int i=0; i<this.Count; i++)
        {
            formatString += "{" + i.ToString() + "} + ";
        }

        formatString = result.TrimEnd((" +").ToCharArray()); // remove the last "+ ";    
        float[] values = this.ToArray();       
        result = String.Format(formatString, values);

        return String.Format("{0} = {1}", result, this.Sum);  
    }
}

Объект Set будет иметь свойство Sum, а также метод ToString(), который будет отображать сумму и все ее содержимое.