Hat, wie vorhergesehen, etwas gedauert, bis ich dazu gekommen bin. Im Prinzip ist es eine C-Implementierung verschiedener Algorithmen der C++-Standardbibliothek. Das ginge sicherlich auch effizienter (insbesondere bei der Rotation weiß ich, dass es effizienter ginge), aber die Beispielimplementierungen für C++-Algorithmen sind immer für ganz allgemeine forward-Iteratoren (wohingegen man hier random-access zur Verfügung hätte). Durch die Vermeidung der Optimierung auf random-access konnte ich dann einfach abschreiben, ohne viel nachzudenken. Außerdem ist es für kleine Kombinationen vermutlich sowieso mindestens gleich schnell wie irgendwas mit memmove oder binärer Suche:
#include <stdio.h>
// Nur für Testausgaben:
void print_combination(int *first, int *last)
{
putchar('{');
if (first != last)
{
printf("%d", *first);
while (++first != last)
printf(", %d", *first);
}
puts("}");
}
void ptr_swap(int *p1, int *p2)
{
int temp = *p1;
*p1 = *p2;
*p2 = temp;
}
void reverse(int *first, int *last)
{
while(first < --last)
{
ptr_swap(first++, last);
}
}
void rotate(int *first, int *middle, int *last)
{
reverse(first, middle);
reverse(middle, last);
reverse(first, last);
}
int next_combination(int *first, int *middle, int *last)
{
if ((first == last) || (first == middle) || (last == middle) || (last == first + 1))
return 0;
int *i1 = middle;
int *i2 = last - 1;
while (first != i1)
{
if (*--i1 < *i2)
{
int *j = middle;
while (!(*i1 < *j)) ++j;
ptr_swap(i1, j);
++i1;
++j;
i2 = middle;
rotate(i1, j, last);
while (last != j)
{
++j;
++i2;
}
rotate(middle, i2, last);
return 1;
}
}
rotate(first, middle, last);
return 0;
}
int main()
{
int combo[] = {1, 2, 3, 4, 5};
const int alphabet_length = sizeof(combo)/ sizeof(*combo);
int i;
for (i = 0; i <= alphabet_length; ++i)
{
printf("Alle Kombinationen der Länge %d:\n", i);
do
{
print_combination(combo, combo + i); // Hier stattdessen dein Code, der irgendwas mit der Kombination macht
}
while (next_combination(combo, combo + i, combo + alphabet_length));
}
return 0;
}
