Перестановка списка строк алгоритма

Question

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

List<string> str = new List<string>{"a", "b", "c", "d"};

Как я могу получить список каждой перестановки, доступной в этом списке?Например,

1. a, b, c, d
2. ab, c, d
3. ab, cd
4. abc, d
5. abcd
6. a, bc, d
7. a, bcd
8. a, b, cd

По какой-то причине я не могу найти образец для начала.Я также хотел бы иметь возможность игнорировать перестановку, когда объединенная строка имеет количество похожих символов X.Таким образом, если бы X было 4, в этом списке число 5 не существовало бы и было бы 7 перестановок.

private List<string> permute(List<string> values, int maxPermutation)
{
     //alittle help on starting it would be great :)
}

Я посмотрел и прочитал это , но он не сохраняетзаказ.

Answer 1

Это довольно просто: у вас есть три места, где вы можете либо поставить запятую, либо ничего не ставить.Существует восемь комбинаций, соответствующих 2 ^ 3 двоичным числам.

Для каждого числа от 0 до 7 включительно, создайте двоичное представлениеПоставьте запятую в каждой позиции, где двоичное представление имеет 1;не ставьте запятую там, где есть ноль.

for (int m = 0 ; m != 8 ; m++) {
    string s = "a";
    if ((m & 1) != 0) s += ",";
    s += "b";
    if ((m & 2) != 0) s += ",";
    s += "c";
    if ((m & 4) != 0) s += ",";
    s += "d";
    Console.WriteLine(s);     
}

Answer 2

Вы можете использовать рекурсивный подход: взять первую букву, построить все возможные комбинации, начиная со второй (это рекурсия ...), и добавить первую букву к каждой из них. Затем возьмите первые две буквы вместе, рекурсивно соберите все комбинации, начиная с третьей. И так далее ...

Что касается дополнительных требований: если вы хотите исключить все «комбинации», содержащие строку с X буквами, просто пропустите это число при построении первой строки.

Answer 3

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

List<string> str = new List<string>{ "a", "h", "q", "z", "b", "d" };
List<List<string>> combinations = combine(str.OrderBy(s=>s).ToList());

List<List<string>> combine(List<string> items)
{
    List<List<string>> all = new List<List<string>>();

    // For each index item in the items array
    for(int i = 0; i < items.Length; i++)
    {
        // Create a new list of string
        List<string> newEntry = new List<string>();
        // Take first i items
        newEntry.AddRange(items.Take(i));
        // Concatenate the remaining items
        newEntry.Add(String.concat(items.Skip(i)));
        // Add these items to the main list
        all.Add(newEntry);

        // If this is not the last string in the list
        if(i + 1 < items.Length)
        {
            // Process sub-strings
            all.AddRange(combine(items.Skip(i + 1).ToList()));
        }
    }
    return all;
}

Если вам нужно создать комбинации (или перестановки, или вариации), тогда Combinatorics - это фантастическая библиотека.

Answer 4

Бинарный подход, приведенный выше, является правильным, и на самом деле это проблема разбиения (но не «проблема разбиения»), а не перестановка.

http://en.wikipedia.org/wiki/Partition_of_a_set

Остерегайтесь, потому что число разделов растет быстрее, чем экспоненциально (e ^ e ^ n), поэтому для больших строк это будет очень медленно.