Нужно сгенерировать каждую уникальную комбинацию массива файлов рекурсивно - PullRequest
Новая
       95

Нужно сгенерировать каждую уникальную комбинацию массива файлов рекурсивно

2 голосов
/ 29 сентября 2010

Я исследовал и нашел ЛОТОВ подобных запросов, но ничего не было достаточно, что мне было нужно.

Вот моя проблема.Я работаю в C #, и у меня есть массив FileInfo [] с неизвестным количеством элементов в нем. 

FileInfo[] files = new FileInfo[]
{
    new FileInfo(@"C:\a.jpg"),
    new FileInfo(@"C:\b.jpg"),
    new FileInfo(@"C:\c.jpg"),
    new FileInfo(@"C:\d.jpg"),
    new FileInfo(@"C:\e.jpg"),
    new FileInfo(@"C:\f.jpg"),
    new FileInfo(@"C:\g.jpg"),
    new FileInfo(@"C:\h.jpg"),
    new FileInfo(@"C:\i.jpg"),
}; // Using 9 elements for this example

И мне нужно сгенерировать список всех возможных комбинаций переупорядочения этих файлов безповторяя файлы.

Итак, некоторые из моих результатов будут такими (пример не в формате кода): 

a, b, c, d, e, f, g, h, i
a, b, c, d, e, f, g, i, h // i & h switched
a, b, c, d, e, f, h, g, i // last 3 elements switched

a, a, b, b, c, c, d, d, e // THIS IS NOT ACCEPTED, because elements are duplicated

И так далее, пока я не придумаю всевозможная комбинация

Таким образом, общее количество результатов должно быть факториалом количества элементов в массиве.В этом примере 9 элементов, поэтому должно быть 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362 880 возможных комбинаций.

Я возился с этимпару дней, и я просто не могу обдумать это.Любая помощь приветствуется, особенно с примерами кода!

Спасибо!

Ответы [ 3 ]

5 голосов
/ 29 сентября 2010

Легко с Linq: 

IEnumerable<FileInfo[]> permutations =
    from a in files
    from b in files.Except(new[] { a })
    from c in files.Except(new[] { a, b })
    from d in files.Except(new[] { a, b, c })
    from e in files.Except(new[] { a, b, c, d })
    from f in files.Except(new[] { a, b, c, d, e })
    from g in files.Except(new[] { a, b, c, d, e, f })
    from h in files.Except(new[] { a, b, c, d, e, f, g })
    from i in files.Except(new[] { a, b, c, d, e, f, g, h })
    select new[] { a, b, c, d, e, f, g, h, i };

РЕДАКТИРОВАТЬ:

Вот общее решение для любого количества предметов: 

static class ExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> source, int count)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() }; 
        for (int i = 0; i < count; i++)
        {
            result =  
                from seq in result 
                from item in source.Except(seq)
                select seq.Concat(new[] { item }); 
        } 
        return result;
    }
}

Используйте его какследует: 

IEnumerable<IEnumerable<FileInfo>> permutations = files.GetPermutations(9);

(Это решение основано на статье Эрика Липперта о декартовых произведениях .)

РЕДАКТИРОВАТЬ 2:

Вотвариант с использованием Aggregate: 

static class ExtensionMethods
{
    public static IEnumerable<IEnumerable<T>> GetPermutations2<T>(this IEnumerable<T> source, int count)
    {
        IEnumerable<IEnumerable<T>> seed = new[] { Enumerable.Empty<T>() }; 
        return Enumerable.Repeat(source, count)
            .Aggregate(
                seed,
                (accumulator, sequence) =>
                    from acc in accumulator
                    from item in sequence.Except(acc)
                    select acc.Concat(new[] { item }));
    }
}
1 голос
/ 29 сентября 2010

Для этого доступны различные алгоритмы. На странице ниже перечислены 3 разных:

Подсчет и перечисление всех перестановок

1 голос
/ 29 сентября 2010

Вы действительно хотите все перестановки набора.

Редактировать: вот пример того, о чем вы говорите: http://www.codeproject.com/KB/recipes/Premutations.aspx

...