Найти допустимые назначения целых чисел в массивах (перестановки с заданным порядком)

Question

У меня общая проблема с поиском хорошего алгоритма генерации каждого возможного назначения для некоторых целых чисел в разных массивах.

Допустим, у меня есть n массивов и m чисел (я могу иметь больше массивов, чем чисел, большечисла, чем массивы или столько же массивов, сколько чисел).

В качестве примера у меня есть числа 1,2,3 и три массива:

{}, {}, {}

Теперь я хотел бы найти каждый изэти решения:

{1,2,3}, { }, { }
{ }, {1,2,3}, { }
{ }, { }, {1,2,3}
{1,2}, {3}, { }
{1,2}, { }, {3}
{ }, {1,2}, {3}
{1}, {2,3}, { }
{1}, { }, {2,3}
{ }, {1}, {2,3}
{1}, {2}, {3}

Так что в основном я хотел бы найти каждую возможную комбинацию, чтобы присвоить номера различным массивам с сохранением порядка.Как и в примере, 1 всегда должен стоять перед остальными и так далее ...

Я хочу написать алгоритм на C ++ / Qt, чтобы найти все эти допустимые комбинации.

Кто-нибудь есть подход для меня, как справиться с этой проблемой?Как бы я сгенерировал эти перестановки?

ДОПОЛНЕНИЯ

К сожалению, мне не удалось изменить замечательные примеры, которые вы дали для моей проблемы, так как числа, которыеЯ хочу расположить массивы, хранящиеся в массиве (или для меня QVector)

Может кто-нибудь помочь мне изменить алгоритм так, чтобы он давал мне каждую возможную действительную комбинацию чисел в QVector в QVector, чтобы я мог выполнять дальнейшие вычисления для каждого из них?

QVector<int> line; // contains the numbers: like {7,3,6,2,1}
QVector< QVector<int> > buckets; // empty buckets for the numbers { {}, {}, {} }

QList< QVector< QVector<int> > > result; // List of all possible results

Было бы здорово, если бы кто-нибудь мог предоставить мне простую реализацию, которая работает, или советы о том, как ее получить ...не удалось изменить уже предоставленный код, чтобы он работал ...

Answer 1

Это будет легко с возвратной рекурсией. Вы должны отслеживать, какой массив вы заполняете, и какой номер вы до. Примерно так:

void gen(int arrayN, int number)
{
   if (number == MAX_NUMBER + 1) //We have a solution
   {
        printSolution();
        return;
   }

   if (arrayN == MAX_ARRAYS + 1) //No solution
       return;

   gen(arrayN + 1, number); //Skip to next array

   for (int i = number; i <= MAX_NUMBER; i++)
   {
       //Save at this line the numbers into an array for the solution
       gen(arrayN + 1, i + 1); //Used the numbers from "number" to "i" inclusive
   }
}

gen(0, 1);

Answer 2

#include <vector>
#include <list>
#include <iostream>

class NestedCollection {
public:
    std::vector<std::list<int> > lists;

    NestedCollection(int n)
    : lists(n, std::list<int>())
    {};

    NestedCollection(const NestedCollection& other)
    : lists(other.lists)
    {};

    std::vector<NestedCollection> computeDistributions(int n, int m, int last_possible_index) {
        std::vector<NestedCollection> result;
        // iterate over all possible lists (invariant: last_possible_index >= i >= 0)
        // or skip if there is no number left to distribute (invariant: m>0)
        for(int i=last_possible_index; i>=0 && m>0 ; --i) {
            NestedCollection variation(*this);
            // insert the next number
            variation.lists[i].push_front(m);
            // recurse with all following numbers
            std::vector<NestedCollection> distributions = variation.computeDistributions(n, m-1, i);
            if(distributions.empty()) // we could also write if(m==1) - this guards the end of the recursion
                result.push_back(variation);
            else
                result.insert(result.end(), distributions.begin(), distributions.end() );
        }
        return result;
    };

    static std::vector<NestedCollection> findAllDistributions(int n, int m) {
        std::vector<NestedCollection> result;
        result = NestedCollection(n).computeDistributions(n, m, n-1);
        return result;
    };
};

int main() {
    int n=3, m=3;
    std::vector<NestedCollection> result = NestedCollection::findAllDistributions(n, m);
    for(std::vector<NestedCollection>::iterator it = result.begin(); it!=result.end(); ++it) {
        for(std::vector<std::list<int> >::iterator jt = it->lists.begin(); jt!=it->lists.end(); ++jt) {
            std::cout<<"{";
            for(std::list<int>::iterator kt = jt->begin(); kt!=jt->end(); ++kt) {
                std::cout<<*kt<<", ";
            }
            std::cout<<"} ";
        }
        std::cout<<std::endl;
    }
    return 0;
}

Answer 3

Это пахнет как рекурсия.Сначала рассчитайте комбинации для помещения m-1 в n массивов.Затем вы получаете еще n решений, помещая первое число в любой из n массивов этих решений.

Answer 4

Разбивается в этом случае, где находятся 2 раздела.Есть 4 возможных местоположения, так что будет 16 комбинаций, но это не потому, что вы удаляете «дубликаты».Немного похоже на плитки домино.Здесь у вас 4 «двойника», а 12 синглов уменьшаются до 6, поэтому у вас есть 10 комбинаций.

Вы можете сгенерировать его, выбрав первое, а затем сгенерировав второе как> = первое.

Первый может быть 0, 1, 2 или 3. 0 означает, что он появляется перед 1. 3 означает, что он появляется после 3.

В ваших 10 решениях выше разделы находятся на:

1: 3 и 3 2: 0 и 3 3: 0 и 0 4: 2 и 3 5: 2 и 2 6: 0 и 2 7: 1 и 3 8: 1 и 1 9: 0 и 1 10: 1 и2

Если вы генерируете в алгоритмическом порядке, вы, вероятно, получите их 0 и 0, 0 и 1, 0 и 2, 0 и 3, 1 и 1, 1 и 2, 1 и 3, 2 и 2,2 и 3, 3 и 3, хотя вы, конечно, можете сделать их в обратном порядке.

В приведенных выше примерах посмотрите на положение запятых и число непосредственно слева от них.Если слева от них нет чисел, то это 0.

Answer 5

Следующий код написан на C #.

class LineList<T> : List<T[][]> 
{
    public override string ToString()
    {
        var sb = new StringBuilder();
        sb.Append(Count).AppendLine(" lines:");
        foreach (var line in this)
        {
            if (line.Length > 0)
            {
                foreach (var bucket in line)
                {
                    sb.Append('{');
                    foreach (var item in bucket)
                    {
                        sb.Append(item).Append(',');
                    }
                    if (bucket.Length > 0)
                    {
                        sb.Length -= 1;
                    }
                    sb.Append("}, ");
                }
                sb.Length -= 2;
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }
}

class Permutor<T>
{
    public T[] Items { get; private set; }
    public bool ReuseBuckets { get; set; }
    private T[] emptyBucket_;
    private Dictionary<int, Dictionary<int, T[]>> buckets_;   // for memoization when ReuseBuckets=true
    public Permutor(T[] items)
    {
        ReuseBuckets = true;  // faster and uses less memory
        Items = items;
        emptyBucket_ = new T[0];
        buckets_ = new Dictionary<int, Dictionary<int, T[]>>();
    }
    private T[] GetBucket(int index, int size)
    {
        if (size == 0)
        {
            return emptyBucket_;
        }
        Dictionary<int, T[]> forIndex;
        if (!buckets_.TryGetValue(index, out forIndex))
        {
            forIndex = new Dictionary<int, T[]>();
            buckets_[index] = forIndex;
        }
        T[] bucket;
        if (!forIndex.TryGetValue(size, out bucket))
        {
            bucket = new T[size];
            Array.Copy(Items, index, bucket, 0, size);
            forIndex[size] = bucket;
        }
        return bucket;
    }
    public LineList<T> GetLines(int bucketsPerLine)
    {
        var lines = new LineList<T>();
        if (bucketsPerLine > 0)
        {
            AddLines(lines, bucketsPerLine, 0);
        }
        return lines;
    }
    private void AddLines(LineList<T> lines, int bucketAllotment, int taken)
    {
        var start = bucketAllotment == 1 ? Items.Length - taken : 0;
        var stop = Items.Length - taken;
        for (int nItemsInNextBucket = start; nItemsInNextBucket <= stop; nItemsInNextBucket++)
        {
            T[] nextBucket;
            if (ReuseBuckets)
            {
                nextBucket = GetBucket(taken, nItemsInNextBucket);
            }
            else
            {
                nextBucket = new T[nItemsInNextBucket];
                Array.Copy(Items, taken, nextBucket, 0, nItemsInNextBucket);
            }
            if (bucketAllotment > 1)
            {
                var subLines = new LineList<T>();
                AddLines(subLines, bucketAllotment - 1, taken + nItemsInNextBucket);
                foreach (var subLine in subLines)
                {
                    var line = new T[bucketAllotment][];
                    line[0] = nextBucket;
                    subLine.CopyTo(line, 1);
                    lines.Add(line);
                }
            }
            else
            {
                var line = new T[1][];
                line[0] = nextBucket;
                lines.Add(line);
            }
        }
    }

}

Эти вызовы ...

var permutor = new Permutor<int>(new[] { 1, 2, 3 });
for (int bucketsPerLine = 0; bucketsPerLine <= 4; bucketsPerLine++)
{
    Console.WriteLine(permutor.GetLines(bucketsPerLine));
}

генерируют этот вывод ...

0 lines:

1 lines:
{1,2,3}

4 lines:
{}, {1,2,3}
{1}, {2,3}
{1,2}, {3}
{1,2,3}, {}

10 lines:
{}, {}, {1,2,3}
{}, {1}, {2,3}
{}, {1,2}, {3}
{}, {1,2,3}, {}
{1}, {}, {2,3}
{1}, {2}, {3}
{1}, {2,3}, {}
{1,2}, {}, {3}
{1,2}, {3}, {}
{1,2,3}, {}, {}

20 lines:
{}, {}, {}, {1,2,3}
{}, {}, {1}, {2,3}
{}, {}, {1,2}, {3}
{}, {}, {1,2,3}, {}
{}, {1}, {}, {2,3}
{}, {1}, {2}, {3}
{}, {1}, {2,3}, {}
{}, {1,2}, {}, {3}
{}, {1,2}, {3}, {}
{}, {1,2,3}, {}, {}
{1}, {}, {}, {2,3}
{1}, {}, {2}, {3}
{1}, {}, {2,3}, {}
{1}, {2}, {}, {3}
{1}, {2}, {3}, {}
{1}, {2,3}, {}, {}
{1,2}, {}, {}, {3}
{1,2}, {}, {3}, {}
{1,2}, {3}, {}, {}
{1,2,3}, {}, {}, {}

Приблизительный размер решения (bucketsPerLine * NumberOfLines) доминирует во времени выполнения.Для этих тестов N - это длина входного массива, а для bucketsPerLine также установлено значение N.

N=10, solutionSize=923780, elapsedSec=0.4, solutionSize/elapsedMS=2286
N=11, solutionSize=3879876, elapsedSec=2.1, solutionSize/elapsedMS=1835
N=12, solutionSize=16224936, elapsedSec=10.0, solutionSize/elapsedMS=1627
N=13, solutionSize=67603900, elapsedSec=47.9, solutionSize/elapsedMS=1411