Ecco una soluzione che memorizza lo stato in una serie di bool. Funziona creando i seguenti stati su ciascuna chiamata Next()
(n = 5, k = 3).
1 1 1 . . Move last 1 right once.
1 1 . 1 . Move last 1 right once.
1 1 . . 1 Move last 1 right once.
1 . 1 1 . Move the second last 1 right once and all 1s from the right back.
1 . 1 . 1 Move last 1 right once.
1 . . 1 1 Move the second last 1 right once (and all 1s from the right back.)
. 1 1 1 . Move the third last 1 right once and all 1s from the right back.
. 1 1 . 1 Move last 1 right once.
. 1 . 1 1 Move the second last 1 right once (and all 1s from the right back.)
. . 1 1 1 Move the third last 1 right once (and all 1s from the right back.)
Questo stato può quindi essere utilizzato per selezionare gli elementi corrispondenti dalla sequenza fornita per ogni stato.
Inizialmente l'inizializzazione.
public static Boolean[] Initialize(Int32 n, Int32 k)
{
return Enumerable.Concat(Enumerable.Repeat(true, k),
Enumerable.Repeat(false, n - k)).ToArray();
}
Il codice per passare alla combinazione successiva (sottosuccessione).
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;
}
Infine alcuni metodi di supporto.
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;
}
}
E un esempio di utilizzo utilizzando una stringa anziché un elenco.
var sequence = "ABCDE";
var state = Initialize(sequence.Count(), 5);
do
{
Console.WriteLine(new String(sequence.Where((_, idx) => state[idx]).ToArray()));
}
while (state.Next());
Avere IEnumerable è dannoso per voi, perché si andando oltre l'elenco più volte, in modo da avere accesso indicizzatore sarebbe un enorme vantaggio per voi. –
DevinB