Разбивка строки в массив из комбинации слов - помогите с алгоритмом, пожалуйста

[ANR]

Всем привет.



Столкнулся с вроде бы простым, с другой стороны не до конца понятным мне алгоритмом, который будет делать следующее.



Из строки вида



Код:

Код: Выделить всё

1 2 3

где цифры - это слова в предложении



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





Код:

Код: Выделить всё

1
1 2
1 3
1 2 3 (собственно сама строка)
1 3 2
2
2 1
2 3
2 1 3
2 3 1
3
3 1
3 2
3 1 2
3 2 1

то есть получается 15 различных комбинаций, включая саму строку. Естественно слов в строке может быть не обязательно 3, а 2 или 5 или даже 10, выше - просто пример.



У меня основная загвоздка в том, как можно обработать более двух слов. комбинации из двух слов можно получить перебором каждого элемента с другим. а как создать комбинации типа "2 3 1" из примера - ломаю голову пока.



Буду благодарен любым советам!



P.S. Пишу на PHP, но тут скорее нужна помощь в самом алгоритме.

[Sham]

примеры алгоритмов комбинаторики ищутся в гугле

тут

пример для C++, который легко переписать для PHP. Хотя там для массива фиксированной длины, но остальные варианты имхо можно перебирать срезами массива разной длины...