Вычисление всех возможных подпоследовательностей заданной длины (C #)
2237 просмотра
4 ответа
Если у меня есть последовательность следующим образом (скажем, это IEnumerable<T>
):
[A, B, C, D, E]
Тогда каков самый чистый способ вычисления всех возможных (непрерывных и не непрерывных) подпоследовательностей заданной длины? Порядок результатов в наборе результатов не важен, но он не должен включать дубликаты.
Например, если я хочу вычислить все возможные подпоследовательности длины 3, набор результатов будет:
[A, B, C]
[A, B, D]
[A, B, E]
[A, C, D]
[A, C, E]
[A, D, E]
[B, C, D]
[B, C, E]
[B, D, E]
[C, D, E]
Напомним, что принятый ниже ответ дал мне хорошую отправную точку, и вот код, с которым я работал, обновлен для использования некоторых из новых методов расширения .NET 3.5:
public static IEnumerable<IEnumerable<T>> Subsequences<T>(
this IEnumerable<T> source,
int count)
{
if (count == 0)
{
yield return Enumerable.Empty<T>();
}
else
{
var skip = 1;
foreach (var first in source)
{
foreach (var rest in source.Skip(skip).Subsequences(count - 1))
{
yield return Enumerable.Repeat(first, 1).Concat(rest);
}
skip++;
}
}
}
Автор: Greg Beech
Источник
Размещён: 13.11.2019 11:51
Ответы (4)
5 плюса
Я имел успех с классом IanG PermuteUtils
:
char[] items = new char[] { 'A', 'B', 'C', 'D', 'E' };
foreach (IEnumerable<char> permutation in PermuteUtils.Permute(items, 3)) {
Console.Write("[");
foreach (char c in permutation) {
Console.Write(" " + c);
}
Console.WriteLine(" ]");
}
Результаты в:
[ABC] [ABD] [ABE] [ACB] [ACD] [ACE] [АБР] [ADC] [ADE] [AEB] [AEC] [AED] [BAC] [ ПЛОХО ] [BAE] [BCA] [BCD] [BCE] [BDA] [BDC] ...Автор: Sean Bright Размещён: 12.05.2009 12:37
1 плюс
Что-то вроде:
static void Main()
{
string[] data = { "A", "B", "C", "D", "E" };
WalkSubSequences(data, 3);
}
public static void WalkSubSequences<T>(IEnumerable<T> data, int sequenceLength)
{
T[] selected = new T[sequenceLength];
WalkSubSequences(data.ToArray(), selected, 0, sequenceLength);
}
private static void WalkSubSequences<T>(T[] data, T[] selected,
int startIndex, int sequenceLength)
{
for (int i = startIndex; i + sequenceLength <= data.Length; i++)
{
selected[selected.Length - sequenceLength] = data[i];
if (sequenceLength == 1)
{
ShowResult(selected);
}
else
{
WalkSubSequences(data, selected, i + 1, sequenceLength - 1);
}
}
}
private static void ShowResult<T>(T[] selected)
{
StringBuilder sb = new StringBuilder();
sb.Append(selected[0]);
for (int j = 1; j < selected.Length; j++)
{
sb.Append(';').Append(selected[j]);
}
Console.WriteLine(sb.ToString());
}
Автор: Marc Gravell
Размещён: 12.05.2009 01:22
0 плюса
Вот решение, хранящее состояние в массиве bools. Он работает путем создания следующих состояний при каждом Next()
вызове (n = 5, k = 3).
1 1 1. , Переместить последнюю 1 вправо один раз. 1 1. 1 Переместить последнюю 1 вправо один раз. 1 1. , 1 Переместите последнюю 1 вправо один раз. 1 1 1. Переместите второй последний 1 вправо один раз и все 1 с правой спины. 1 1 1 Переместите последнюю 1 вправо один раз. 1 , 1 1 Переместите второй последний 1 вправо один раз (и все 1 с правой спины.) , 1 1 1. Переместите третий последний 1 вправо один раз и все 1 с правой спины. , 1 1. 1 Переместите последнюю 1 вправо один раз. , 1 1 1 Переместите второй последний 1 вправо один раз (и все 1 с правой спины.) , , 1 1 1 Переместите третий последний 1 вправо один раз (и все 1 с правой спины.)
Это состояние затем может быть использовано для выбора базовых элементов из предоставленной последовательности для каждого состояния.
Сначала инициализация.
public static Boolean[] Initialize(Int32 n, Int32 k)
{
return Enumerable.Concat(Enumerable.Repeat(true, k),
Enumerable.Repeat(false, n - k)).ToArray();
}
Код для перехода к следующей комбинации (подпоследовательность).
public static Boolean Next(this Boolean[] list)
{
Int32 lastOneIndex = Array.LastIndexOf(list, true);
if (lastOneIndex == -1)
{
return false; // All zeros. 0000000
}
else if (lastOneIndex < list.Length - 1)
{
// Move the last one right once. 1100X00 => 11000X0
list.MoveBlock(lastOneIndex, lastOneIndex, lastOneIndex + 1);
}
else
{
Int32 lastZeroIndex = Array.LastIndexOf(list, false, lastOneIndex);
if (lastZeroIndex == -1)
{
return false; // All ones. 1111111
}
else
{
Int32 blockEndIndex = Array.LastIndexOf(list, true, lastZeroIndex);
if (blockEndIndex == -1)
{
// Move all ones back to the very left. 0000XXX => XXX0000
list.MoveBlock(lastZeroIndex + 1, lastOneIndex, 0);
return false; // Back at initial position.
}
else
{
// Move the block end right once. 11X0011 => 110X011
list.MoveBlock(blockEndIndex, blockEndIndex, blockEndIndex + 1);
// Move the block of ones from the very right back left. 11010XX => 1101XX0
list.MoveBlock(lastZeroIndex + 1, lastOneIndex, blockEndIndex + 2);
}
}
}
return true;
}
Наконец несколько вспомогательных методов.
public static void MoveBlock(this Boolean[] list, Int32 oldStart, Int32 oldEnd, Int32 newStart)
{
list.ClearBlock(oldStart, oldEnd);
list.SetBlock(newStart, newStart + oldEnd - oldStart);
}
public static void SetBlock(this Boolean[] list, Int32 start, Int32 end)
{
list.SetBlockToValue(start, end, true);
}
public static void ClearBlock(this Boolean[] list, Int32 start, Int32 end)
{
list.SetBlockToValue(start, end, false);
}
public static void SetBlockToValue(this Boolean[] list, Int32 start, Int32 end, Boolean value)
{
for (int i = start; i <= end; i++)
{
list[i] = value;
}
}
И пример использования с использованием строки вместо списка.
var sequence = "ABCDE";
var state = Initialize(sequence.Count(), 5);
do
{
Console.WriteLine(new String(sequence.Where((_, idx) => state[idx]).ToArray()));
}
while (state.Next());
Автор: Daniel Brückner
Размещён: 12.05.2009 03:17
0 плюса
Я бы предложил рекурсивный алгоритм для этого. Извините, но я давно уже ничего не делал в C #, поэтому я просто приведу здесь псевдокод.
function allPossible(iterator, length, currSubSeq, allResults) {
// Add the current sub sequence to the results if it is the correct length.
if (currSubSeq.length == length) {
copy = currSubSeq.copy();
allResults.add(copy);
}
// If it is too long, return early.
else if (currSubSeq.length > length) {
return allResults;
}
// Get the next item from the iterator and handle both cases:
// I.E. when it is, and when it isn't in a sub sequence.
item = iterator.getNext();
allPossible(iterator, currSubSeq, allResults);
currSubSeq.add(item);
allPossible(iterator, currSubSeq, allResults);
return allResults;
}
Затем вы находите все возможные подпоследовательности, вызывая allPossible
оператор, iterator
который производит все элементы в вашей исходной последовательности, для length
которого вы хотите получить свои подпоследовательности, пустую последовательность элементов для currSubSeq
и пустую последовательность последовательностей элементов allResults
. Я предполагаю семантику передачи по ссылке для всех параметров. Извините, что я не смог дать вам правильную реализацию C #, но я уверен, что вы знаете более чем достаточно, чтобы взять набросок моего алгоритма и превратить его в код.
Последняя вещь. Поскольку этот алгоритм является рекурсивным, у вас может быть переполнение стека, если вы запускаете его на очень длинной последовательности с большим length
параметром, поскольку использование стека равно O (2 ^ N), где N = length
. Я не думаю, что это большая проблема, потому что алгоритм имеет O (2 ^ N) времени выполнения из-за характера проблемы, поэтому вы не должны пытаться запустить его с достаточно большим, length
чтобы переполнить стек в любом случае!
ПРОСМОТР Я на самом деле не тестировал этот псевдокод, так что может быть что-то тонкое, о чем я не думал.
Автор: A. Levy Размещён: 12.05.2009 01:32Вопросы из категории :
- c# Преобразовать десятичную в двойную?
- c# Как рассчитать чей-то возраст в C #?
- c# Как вы сортируете словарь по значению?
- c# В чем разница между int и Integer в Java и C #?
- c# Как создать новый экземпляр объекта из Типа
- c# Datatable против Dataset
- c# Setting Objects to Null/Nothing after use in .NET
- c# Конвертировать целые числа в записанные числа
- c# Почему я не могу иметь абстрактные статические методы в C #?
- c# Как я могу оценить код C # динамически?
- algorithm Функция для создания цветовых колес
- algorithm Big O, как вы рассчитываете / приближаете это?
- algorithm Пиковое обнаружение измеренного сигнала
- algorithm Головоломка: Найти самый большой прямоугольник (проблема максимального прямоугольника)
- algorithm Объединить Сортировать связанный список
- algorithm Алгоритм нахождения наибольшего простого множителя числа
- algorithm Алгоритм сравнения двух изображений
- algorithm Как я могу измерить сходство между двумя изображениями?
- algorithm Рассчитать расстояние между двумя точками широты и долготы? (Формула Haversine)
- algorithm Как обнаружить дубликаты данных?