Java/Algoritmy/Výpočet permutrací

Z Wikiknih
Skočit na navigaci Skočit na vyhledávání

Algoritmus pro nalezení všech permutací znaků (bez opakování, v jazyku Java)

public static List<String> permutaceBezOpakovani(String pouzitelneZnaky) {

        List<String> list = new ArrayList<String>(faktorial(pouzitelneZnaky.length())/*(1)*/);

        if (pouzitelneZnaky.length() == 1) { /*(2)*/
            list.add(pouzitelneZnaky);
            return list;
        }

        for (int i = 0; i < pouzitelneZnaky.length(); i++) { /*(3)*/
            char c = pouzitelneZnaky.charAt(i);
            List<String> l = permutaceBezOpakovani(vynechatCharAt(pouzitelneZnaky, i)/*(4)*/);
            for (String podPerm/*(5)*/ : l) {
                list.add(c + podPerm); /*(6)*/
            }
        }
        return list;
    }
  1. Počet permutací bez opakování je dán jako w:faktoriál použitelných prvků. Tato metoda v Javě standardně není, viz faktorial
  2. Permutací jediného prvku je jednoprvková množina, obsahující právě tento prvek
  3. Každý znak se musí vyskytovat na prvním místě, za ním jsou pak další permutace zbývajících znaků (předpokladem je rekurze)
  4. Metoda vynechatCharAt - jde o inverzi metody charAt ze třídy String, vrací celý vzorový řetězec, s výjimkou příslušného znaku.
  5. podPerm = postupně každý z řetězců vrácených permutací o úroveň níže.
  6. Přidá do výstupního (vraceného) seznamu příslušný prvek.