[c++] PERMUTACJE

Witam.Mam zadanie na za 2 tygodnie. do zrobienia pewna permutacje przykladowo mam 3 liczby lub wiecej i zeby wypisal wszytskie mozliwe kombinacje.

np. 123 to:

123
132
213
231
312
321

nie mam juz pomyslu jak to zrobic technicznie. Nie prosze ogotowy program, bo lubie programowac i cche zrozumiec to co mam napisac. ALe chcialem prosic o jakas podpowiedz. jak to najlepiej zrobic

Dla kolejnosci leksykograficznej:

mamy tablice z roznymi cyframi ulozonymi rosnaco a[] = {1, 2, 3}

1. wypisz to co w tablicy
2. idac od prawej znajdz takie i, ze a[i] < a[i + 1]
   2a. na prawo od i znajdz najmniejszy wiekszy od a[i] (bedzie na pozycji j)
   2b. zamien a[i] z a[j]
   2c. odwroc kolejnosc na prawo od i
   2d. wypisz to co w tablicy
3. idz do 2

Wszystko sie konczy gdy w 2 nie znajdzie sie spelniajacego warunek elementu

jak nie trzeba w kolejnosci leksykograficznej to poszukaj o tablicy inwersji i silnia systemie

http://4programmers.net/Forum/viewtopic.php/id=47698

// Albo też roszkę inaczej : powiedzmy że ciąg znaków traktujesz jak liczbe, każdy jeden znak jak kolejną cyferkę. Zaczynasz od dolnej wartości, od min, potem zwiększasz ostatni znak/cyferkę, aż dojdzie do wartości max+1. Przy max+1 zerujesz ostatnia cyfrę (min), zwiększasz przedostatnia cyferkę o 1 i znow sprawdzasz czy nie jest równa max+1 i tak w kólko do cyferki pierwszej, jak juz wszystkie mają max a ostatnia max+1 to koniec. Mankament jest jeden z zakresu 0..255 możesz wykorzystać tylko 0..254.

// Albo też roszkę inaczej : powiedzmy że ciąg znaków traktujesz jak liczbe, każdy jeden znak jak kolejną cyferkę. Zaczynasz od dolnej wartości, od min, potem zwiększasz ostatni znak/cyferkę, aż dojdzie do wartości max+1. Przy max+1 zerujesz ostatnia cyfrę (min), zwiększasz przedostatnia cyferkę o 1 i znow sprawdzasz czy nie jest równa max+1 i tak w kólko do cyferki pierwszej, jak juz wszystkie mają max a ostatnia max+1 to koniec. Mankament jest jeden z zakresu 0..255 możesz wykorzystać tylko 0..254.

To nie bedzie wypisywac permutacji tylko wszystkie mozliwe wyniki losowan 3 liczb z 3 ze ZWRACANIEM (czyli z powtorzeniami). Ma nie byc powtorzen. A jesli dodasz sprawdzanie powtorzen, to Twoj algorytm bedzie miec duzo gorsza zlozonosc od tego co podal foflik.

// co do permutacji fakt, nawet sie nie zastanowiłem, że ma byc bez powtórzeń, przeróbka nie ma sensu, bo rzeczywiście ze złożonością będzie jeszcze gorzej [mf]

w Pascalu można tak

var  a:string; //indeksy od jedynki

procedure permute(k:integer);
var i:integer; t:char;
begin
  if k=1 then writeln(a)
  else begin
    permute(k-1);
    for i:=1 to k-1 do begin
      t:=a[i]; a[i]:=a[k]; a[k]:=t;
      permute(k-1);
      t:=a[i]; a[i]:=a[k]; a[k]:=t;
    end
  end
end;

begin
  a:='abcde';
  permute(length(a));
end.

wg. N. Wirth "Modula 2"