Wariacje bez powtórzeń zbioru n-elementowego

Witam, mam następujący problem algorytmiczny, czy ktoś mógłby mi pomóc napisać program, który wygeneruje wszystkie wariacje bez powtórzeń o długości N, dla zbioru cyfr tab[10]={ 0,1,2,3,4,5,6,7,8,9}.
Czyli np.:
Jeśli N = 3, to przykładowe wariacje:
1 2 3
1 3 2
1 4 3
1 7 8
1 9 4
9 3 1 itd itd..

Moim problemem jest zaimplementowanie tego dla nieznanego z góry N, bo gdybym znał z góry N, to mógłbym sobie zrobić N zagnieżdżonych pętli "for" : )

Z góry dzięki!

i takie zagnieżdżenie możesz zrobić rekurencją:

rec(d)
    if (n==d) 
        r[1..n] to kolejna kombinacja
    else
        for i= r[d]+1 .. n
            r[d+1] = i
            rec(d+1)

a wołasz to
r[0]=0
rec(0)

Nie do końca zrozumiałem Twoją odpowiedź, tablica r[] to tablica, która będzie przechowywała kolejne wariacje?

za każdym razem gdy d==n w tablicy r[] jest jedna kambinacja

Dalej nie moge sobie z tym dac rady, moglbym prosic o jakas przykladowa implementacje w Javie albo Cpp?

sorry, pętla powinna kręcić się nie do "n" ale do "k" co jednak dość łatwo można było zauważyć
przepraszam, za zmyłkę
demo w C http://ideone.com/DUkWo

int r[100], n, k;
 
void rec(int d){
        int i;
        if (n==d) {
                for( i=1; i<=n; i++ )
                        printf("%d ", r[i]);
                puts("");
        } else
                for( i= r[d]+1; i<=k; i++ ){ // ew. for( i=1; i<=k; i++ )
                        r[d+1] = i;
                        rec(d+1);}}
 
main(){
        n=3; k=5; r[0]=0;
        rec(0);}

Twój program przyjmuje, że wariacja 1 2 3 jest równoważna 1 3 2, a one są zupełnie różne : )

pilon napisał(a)

[...] Moim problemem jest zaimplementowanie tego dla nieznanego z góry N, bo gdybym znał z góry N, to mógłbym sobie zrobić N zagnieżdżonych pętli "for" [...]

Dopisz sobie permutacje i będziesz miał

Ja bym zrobił taką funkcję rekurencyjną:

def wariacje(elementy,maska,n,curr,ret):
   if n==0: 
      ret.append(curr)
      return;
   for i,el in enumerate(elementy):
      if maska[i]==0:
         maska[i]=1
         wariacje(elementy,maska,n-1,curr+(el,),ret)
         maska[i]=0
war=[]
wariacje([1,2,3,4,5,6,7,8,9],[0]*9,3,(),war)
      

Jeżeli m to długość tablicy elementy, to ta funkcja będzie wywoływana m!/(m-n)! i za każdym razem musimy przejść m elementów, więc ogólna ilość operacji jest rzędu O(m*m!/(m-n)), więc narzutem na każdą wariację jest jedno przejście całej tablicy elementów.