Kombinacja bez powtórzeń - zamiana rekurencji w iterację

Odpowiedz Nowy wątek
2014-04-08 12:52

Rejestracja: 6 lat temu

Ostatnio: 5 lat temu

0

Cześć to mój pierwszy post, proszę o wyrozumiałość :)
Mam problem z przekształceniem rekurencyjnej kombinacji w iterację:
Wejście:

  • arr - tablica elemntów, len - ilość kombinacji, startPosition - początek nastepnej iteracji, result - wynik rekurencji

    
    static void combinations2(String[] arr, int len, int startPosition, String[] result) {
    
        if (len == 0) {
            for (String n : result) {
                System.out.print(n + "  \n");
            }
    
                 return;
        }
    
        for (int i = startPosition; i <= arr.length - len; i++) {
            result[result.length - len] = arr[i];
            combinations2(arr, len - 1, i + 1, result);
        }
        ile++;
    }

Próbuje tą rekurencję zamienić na model iteracyjny z odkładaniem zmiennych na stosie, lecz nie wiem co zrobić z instrukcją return; . Czy podejście jest poprawne?

static void combinations2(String[] arr, int len, int startPosition, String[] result) {

        Stack<Integer> start = new Stack<>();
        Stack<Integer> length = new Stack<>();

        start.push(startPosition);
        length.push(len);

        while (len > 0) {
            startPosition = start.pop();
            len = length.pop();

            if (len == 0) {
                for (String n : result) {
                    System.out.print(n + "  \n");                 
                }
               //return;
            } 

            for (int i = startPosition; i <= arr.length - len; i++) {
                result[result.length - len] = arr[i];
                //combinations2(arr, len - 1, i + 1, result);
                start.push(i + 1);
                length.push(len - 1);
                break;
            }
            ile++;
        }  
    }

Dzięki za każdą pomoc.

Pozostało 580 znaków

2014-04-08 14:35

Rejestracja: 6 lat temu

Ostatnio: 9 miesięcy temu

Lokalizacja: Kraków

0

Po pierwsze na pewno ten break w nie ma sensu w pętli bo w takim razie wykona się tylko raz.

Po "break" wróci do while - piotrowicki 2014-04-08 15:03
to jest get(0) pattern :d - remigio 2014-04-08 15:42

Pozostało 580 znaków

2014-04-08 15:43
0

Kolego odnośnie javy to masz mega ilość odpowiedzi. wystarczy wpisać : java iteration example i np. http://www.oopweb.com/Java/Do[...]/ThinkCSJav/Volume/chap06.htm

Pozostało 580 znaków

2014-04-09 15:12

Rejestracja: 6 lat temu

Ostatnio: 5 lat temu

0

Jakbym znalazł odpowiedz nie prosił bym o pomoc :) Czyli nikt nie podpowie jak rozłożyć tę rekurencję na ciąg iteracji?

Pozostało 580 znaków

2014-04-09 15:33
Moderator

Rejestracja: 11 lat temu

Ostatnio: 1 dzień temu

0

Jakbyś napisał co funkcja combinations2 ma robić, to może by się komuś chciało zastanawiać.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

2014-04-10 11:42

Rejestracja: 6 lat temu

Ostatnio: 5 lat temu

0

Tak jak w drugim zdaniu. Dokładniej kombinacja bez powtórzeń k elementów ze zbioru n gdzie, k < n

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0