Generovat seznam všech možných permutací řetězce

hlasů
143

Jak bych mohl jít o generování seznamu všech možných permutací řetězce mezi x a y charaktery na délku, která obsahuje variabilní seznam znaků.

Jakýkoli jazyk bude fungovat, ale to by mělo být přenosné.

Položena 02/08/2008 v 07:57
zdroj uživatelem
V jiných jazycích...                            


35 odpovědí

hlasů
67

Existuje několik způsobů, jak toho dosáhnout. Běžné metody používat rekurzi, memoization nebo dynamické programování. Základní myšlenkou je, že vytvoří seznam všech řetězců délky 1, potom v každé iteraci, pro všechny řetězce vyráběné v poslední iteraci, přidejte tento řetězec zřetězené každý znak v řetězci samostatně. (Proměnná index v kódu níže udržuje na začátku poslední a příští iteraci)

Některé pseudocode:

list = originalString.split('')
index = (0,0)
list = [""]
for iteration n in 1 to y:
  index = (index[1], len(list))
  for string s in list.subset(index[0] to end):
    for character c in originalString:
      list.add(s + c)

byste pak je třeba, aby se odstranily všechny řetězce méně než x na délku, to bude první (x-1) * Len (originalString) položky v seznamu.

Odpovězeno 02/08/2008 v 08:48
zdroj uživatelem

hlasů
35

Je lepší používat ústupek

#include <stdio.h>
#include <string.h>

void swap(char *a, char *b) {
    char temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void print(char *a, int i, int n) {
    int j;
    if(i == n) {
        printf("%s\n", a);
    } else {
        for(j = i; j <= n; j++) {
            swap(a + i, a + j);
            print(a, i + 1, n);
            swap(a + i, a + j);
        }
    }
}

int main(void) {
    char a[100];
    gets(a);
    print(a, 0, strlen(a) - 1);
    return 0;
}
Odpovězeno 10/01/2012 v 19:00
zdroj uživatelem

hlasů
24

Chystáte se dostat hodně řetězců, to je jisté ...

\ sum_ {i = x} ^ y {\ frac {r!} {{(ri)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7B% 20% 5Cfrac% 7BR% 7D% 7B% 7B (ri)% 7D% 7D% 20% 7D!
V případě, x a y je, jak je definovat a r je počet znaků, které vybíráme z - -pokud jsem pochopit, že správně. Určitě byste měli vytvářet nich podle potřeby a ne dostat nedbalý a říkají, generovat POWERSET a filtrovat délku řetězce.

Následující rozhodně není nejlepší způsob, jak generovat tyto, ale je to zajímavý stranou, none-the-méně.

Knuth (objem 4, chomáč 2, 7.2.1.3), nám říká, že (s, t) -combination je ekvivalentní s + 1, co vzít t v čase s opakováním - (S, t) -combination je notace používá Knuth, která je rovna {t \ vybrat {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Můžeme přijít na to, že se nejprve generuje každý (S, T) -combination v binární formě (tak, délky (s + t)) a počítání počtu 0 k levé straně každého 1.

10001000011101 -> stane permutace: {0, 3, 4, 4, 4, 1}

Odpovězeno 05/08/2008 v 05:57
zdroj uživatelem

hlasů
14

Bez rekurzivní řešení podle Knuth, Python například:

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]<perm[i+1]:
            k0=i
    if k0 == None:
        return None

    l0 = k0+1
    for i in range(k0+1, len(perm)):
        if perm[k0] < perm[i]:
            l0 = i

    perm[k0], perm[l0] = perm[l0], perm[k0]
    perm[k0+1:] = reversed(perm[k0+1:])
    return perm

perm=list("12345")
while perm:
    print perm
    perm = nextPermutation(perm)
Odpovězeno 09/11/2010 v 14:58
zdroj uživatelem

hlasů
12

Existuje mnoho dobrých odpovědí zde. také navrhuji velmi jednoduché rekurzivní řešení v jazyce C ++.

#include <string>
#include <iostream>

template<typename Consume>
void permutations(std::string s, Consume consume, std::size_t start = 0) {
    if (start == s.length()) consume(s);
    for (std::size_t i = start; i < s.length(); i++) {
        std::swap(s[start], s[i]);
        permutations(s, consume, start + 1);
    }
}

int main(void) {
    std::string s = "abcd";
    permutations(s, [](std::string s) {
        std::cout << s << std::endl;
    });
}

Poznámka : Řetězce s opakujících se znaků nebude produkovat jedinečné permutace.

Odpovězeno 08/01/2014 v 12:00
zdroj uživatelem

hlasů
12

Zde je jednoduché řešení v jazyce C #.

Generuje pouze odlišné permutace daného řetězce.

    static public IEnumerable<string> permute(string word)
    {
        if (word.Length > 1)
        {

            char character = word[0];
            foreach (string subPermute in permute(word.Substring(1)))
            {

                for (int index = 0; index <= subPermute.Length; index++)
                {
                    string pre = subPermute.Substring(0, index);
                    string post = subPermute.Substring(index);

                    if (post.Contains(character))
                            continue;                       

                    yield return pre + character + post;
                }

            }
        }
        else
        {
            yield return word;
        }
    }
Odpovězeno 05/07/2010 v 10:06
zdroj uživatelem

hlasů
12

Některé pracovní kód Java založené na Sarp své odpovědi :

public class permute {

    static void permute(int level, String permuted,
                    boolean used[], String original) {
        int length = original.length();
        if (level == length) {
            System.out.println(permuted);
        } else {
            for (int i = 0; i < length; i++) {
                if (!used[i]) {
                    used[i] = true;
                    permute(level + 1, permuted + original.charAt(i),
                       used, original);
                    used[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = "hello";
        boolean used[] = {false, false, false, false, false};
        permute(0, "", used, s);
    }
}
Odpovězeno 04/04/2010 v 19:18
zdroj uživatelem

hlasů
12

Dalo by se podívat na „ Efektivní Výčet podskupin Set “, který popisuje algoritmus dělat část toho, co chcete - rychle vytvářet všechny podmnožiny N znaků z délka x do y. Obsahuje implementaci v C.

U každé podskupiny, měli byste ještě generovat všechny permutace. Například, pokud jste chtěli 3 znaky z „abcde“, by vás tento algoritmus dát „abc“, „Abd“, „Abe“ ... ale bude muset k permutaci každý z nich dostat „ACB“, „BAC“, "BCA", atd.

Odpovězeno 14/11/2008 v 20:36
zdroj uživatelem

hlasů
8

Jen jsem šlehanou to až rychle v Ruby:

def perms(x, y, possible_characters)
  all = [""]
  current_array = all.clone
  1.upto(y) { |iteration|
    next_array = []
    current_array.each { |string|
      possible_characters.each { |c|
        value = string + c
        next_array.insert next_array.length, value
        all.insert all.length, value
      }
    }
    current_array = next_array
  }
  all.delete_if { |string| string.length < x }
end

Dalo by se podívat do jazyka API pro vestavěnou funkcí typu permutace, a byste měli být schopni psát více optimalizovaný kód, ale v případě, že čísla jsou tak vysoké, nejsem si jistý, že je hodně způsobem, kolem které mají spoustu výsledků ,

Tak jako tak, myšlenka kódu je začít s řetězcem o délce 0, pak sledovat všechny struny délky Z, kde Z je aktuální velikost v iteraci. Pak se projít každý řetězec a připojit každý znak na každou strunu. Nakonec, při uzavření, odstranit všechny, které byly nižší než x prahovou hodnotou, a vrátí výsledek.

Jsem se vyzkoušet s potenciálně nesmyslným vstupem (seznam znak NULL, podivné hodnoty x a y, atd).

Odpovězeno 02/08/2008 v 08:56
zdroj uživatelem

hlasů
7

Ruby odpověď, která funguje:

class String
  def each_char_with_index
    0.upto(size - 1) do |index|
      yield(self[index..index], index)
    end
  end
  def remove_char_at(index)
    return self[1..-1] if index == 0
    self[0..(index-1)] + self[(index+1)..-1]
  end
end

def permute(str, prefix = '')
  if str.size == 0
    puts prefix
    return
  end
  str.each_char_with_index do |char, index|
    permute(str.remove_char_at(index), prefix + char)
  end
end

# example
# permute("abc")
Odpovězeno 20/04/2012 v 01:21
zdroj uživatelem

hlasů
7

obměňovat (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [( * B C), (C B * )] -> [( * A BC ), (B C), (BC A * ), ( * A CB), (C B), (CB A * )] pro odstranění duplicitních při vložení každé kontrole abeceda aby zjistil, zda předcházející řetězec končí stejným abecedy (proč? -exercise)

public static void main(String[] args) {

    for (String str : permStr("ABBB")){
        System.out.println(str);
    }
}

static Vector<String> permStr(String str){

    if (str.length() == 1){
        Vector<String> ret = new Vector<String>();
        ret.add(str);
        return ret;
    }

    char start = str.charAt(0);
    Vector<String> endStrs = permStr(str.substring(1));
    Vector<String> newEndStrs = new Vector<String>();
    for (String endStr : endStrs){
        for (int j = 0; j <= endStr.length(); j++){
            if (endStr.substring(0, j).endsWith(String.valueOf(start)))
                break;
            newEndStrs.add(endStr.substring(0, j) + String.valueOf(start) + endStr.substring(j));
        }
    }
    return newEndStrs;
}

Vytiskne všechny permutace sans duplikáty

Odpovězeno 22/02/2011 v 19:45
zdroj uživatelem

hlasů
7

... a tady je verze C:

void permute(const char *s, char *out, int *used, int len, int lev)
{
    if (len == lev) {
        out[lev] = '\0';
        puts(out);
        return;
    }

    int i;
    for (i = 0; i < len; ++i) {
        if (! used[i])
            continue;

        used[i] = 1;
        out[lev] = s[i];
        permute(s, out, used, len, lev + 1);
        used[i] = 0;
    }
    return;
}
Odpovězeno 07/02/2011 v 22:56
zdroj uživatelem

hlasů
7

Perl, pokud chcete omezit sami na malými písmeny abecedy, můžete to udělat:

my @result = ("a" .. "zzzz");

To dává všechny možné nitky mezi 1 a 4 znaky pomocí malá písmena. Pro velká písmena, změnit "a"se "A"a "zzzz"k "ZZZZ".

Pro smíšené případě, že dostane mnohem těžší, a pravděpodobně není proveditelné s jedním z Perl vestavěných operátorů, jako je to.

Odpovězeno 15/02/2009 v 11:02
zdroj uživatelem

hlasů
7

Zde je jednoduchý slovo C # rekurzivní řešení:

Metoda:

public ArrayList CalculateWordPermutations(string[] letters, ArrayList words, int index)
        {
            bool finished = true;
            ArrayList newWords = new ArrayList();
            if (words.Count == 0)
            {
                foreach (string letter in letters)
                {
                    words.Add(letter);
                }
            }

            for(int j=index; j<words.Count; j++)
            {
                string word = (string)words[j];
                for(int i =0; i<letters.Length; i++)
                {
                    if(!word.Contains(letters[i]))
                    {
                        finished = false;
                        string newWord = (string)word.Clone();
                        newWord += letters[i];
                        newWords.Add(newWord);
                    }
                }
            }

            foreach (string newWord in newWords)
            {   
                words.Add(newWord);
            }

            if(finished  == false)
            {
                CalculateWordPermutations(letters, words, words.Count - newWords.Count);
            }
            return words;
        }

Povolání:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
Odpovězeno 20/10/2008 v 01:17
zdroj uživatelem

hlasů
7

Rekurzivní roztok v jazyce C ++

int main (int argc, char * const argv[]) {
        string s = "sarp";
        bool used [4];
        permute(0, "", used, s);
}

void permute(int level, string permuted, bool used [], string &original) {
    int length = original.length();

    if(level == length) { // permutation complete, display
        cout << permuted << endl;
    } else {
        for(int i=0; i<length; i++) { // try to add an unused character
            if(!used[i]) {
                used[i] = true;
                permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
                used[i] = false;
            }
        }
}
Odpovězeno 29/09/2008 v 02:34
zdroj uživatelem

hlasů
7

Jedná se o překlad Mikeova Ruby verze, do Common Lisp:

(defun perms (x y original-string)
  (loop with all = (list "")
        with current-array = (list "")
        for iteration from 1 to y
        do (loop with next-array = nil
                 for string in current-array
                 do (loop for c across original-string
                          for value = (concatenate 'string string (string c))
                          do (push value next-array)
                             (push value all))
                    (setf current-array (reverse next-array)))
        finally (return (nreverse (delete-if #'(lambda (el) (< (length el) x)) all)))))

A další verze, o něco kratší a použití více loop facility funkce:

(defun perms (x y original-string)
  (loop repeat y
        collect (loop for string in (or (car (last sets)) (list ""))
                      append (loop for c across original-string
                                   collect (concatenate 'string string (string c)))) into sets
        finally (return (loop for set in sets
                              append (loop for el in set when (>= (length el) x) collect el)))))
Odpovězeno 16/09/2008 v 06:15
zdroj uživatelem

hlasů
6

Následující rekurze vytiskne Java všechny permutace daného řetězce:

//call it as permut("",str);

public void permut(String str1,String str2){
    if(str2.length() != 0){
        char ch = str2.charAt(0);
        for(int i = 0; i <= str1.length();i++)
            permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                     str2.substring(1,str2.length()));
    }else{
    System.out.println(str1);
    }
}

Následující text je aktualizovaná verze výše uvedené „PERMUT“ metoda, která umožňuje n! (N faktoriál) méně rekurzivní volání v porovnání s výše uvedenou metodou

//call it as permut("",str);

public void permut(String str1,String str2){
   if(str2.length() > 1){
       char ch = str2.charAt(0);
       for(int i = 0; i <= str1.length();i++)
          permut(str1.substring(0,i) + ch + str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }else{
    char ch = str2.charAt(0);
    for(int i = 0; i <= str1.length();i++)
        System.out.println(str1.substring(0,i) + ch +    str1.substring(i,str1.length()),
                 str2.substring(1,str2.length()));
   }
}
Odpovězeno 19/06/2013 v 05:23
zdroj uživatelem

hlasů
5

Zde je non-rekurzivní verzi jsem přišel, v javascriptu. Není to na základě non-rekurzivní jedné Knuthův výše, i když má některé podobnosti v elementu odkládání. Jsem ověřil jejich správnost vstupních polí až 8 prvků.

Rychlý optimalizace by být předem flighting na outpole a vyhýbat push().

Základní myšlenka je:

  1. Vzhledem k tomu, jediný zdroj pole, generování prvního novou sadu polí, které swap první prvek s každou další prvek podle pořadí, pokaždé ponechat ostatní prvky klidný. např: vzhledem k tomu, 1234, vytvářet 1234, 2134, 3214, 4231.

  2. Použití každé pole z předchozího průchodu jako semeno pro novou průchodu, ale místo odkládání první prvek, vyměnit druhý prvek s každým následujícím prvkem. Také tentokrát neobsahují původní pole ve výstupu.

  3. Opakujte krok 2, dokud udělat.

Zde je ukázkový kód:

function oxe_perm(src, depth, index)
{
    var perm = src.slice();     // duplicates src.
    perm = perm.split("");
    perm[depth] = src[index];
    perm[index] = src[depth];
    perm = perm.join("");
    return perm;
}

function oxe_permutations(src)
{
    out = new Array();

    out.push(src);

    for (depth = 0; depth < src.length; depth++) {
        var numInPreviousPass = out.length;
        for (var m = 0; m < numInPreviousPass; ++m) {
            for (var n = depth + 1; n < src.length; ++n) {
                out.push(oxe_perm(out[m], depth, n));
            }
        }
    }

    return out;
}
Odpovězeno 03/08/2011 v 08:11
zdroj uživatelem

hlasů
5
import java.util.*;

public class all_subsets {
    public static void main(String[] args) {
        String a = "abcd";
        for(String s: all_perm(a)) {
            System.out.println(s);
        }
    }

    public static Set<String> concat(String c, Set<String> lst) {
        HashSet<String> ret_set = new HashSet<String>();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet<String> all_perm(String a) {
        HashSet<String> set = new HashSet<String>();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i<a.length(); i++) {
                set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
            }
        }
        return set;
    }
}
Odpovězeno 24/10/2010 v 23:01
zdroj uživatelem

hlasů
4

Nejsem si jistý, proč byste chtěli, aby to v první řadě. Výsledný soubor pro jakékoliv středně velké hodnoty x a y budou obrovské, a bude růst exponenciálně jako x a / nebo y se zvětší.

Řekněme, že váš soubor možných charakterů je se 26 malá písmena abecedy, a ptáte se vaše aplikace pro generování všechny obměny, kde délka = 5. Za předpokladu, že nemají dostatek paměti dostanete 11,881,376 (tj 26 k síle 5) řetězce zpět. Narazit, že délka až 6, a budete mít 308,915,776 řetězce zpět. Tato čísla dostat bolestně velký, velmi rychle.

Zde je řešení, které jsem dal dohromady v Javě. Budete muset poskytnout dvě runtime argumenty (v souladu s x a y). Bavit.

public class GeneratePermutations {
    public static void main(String[] args) {
        int lower = Integer.parseInt(args[0]);
        int upper = Integer.parseInt(args[1]);

        if (upper < lower || upper == 0 || lower == 0) {
            System.exit(0);
        }

        for (int length = lower; length <= upper; length++) {
            generate(length, "");
        }
    }

    private static void generate(int length, String partial) {
        if (length <= 0) {
            System.out.println(partial);
        } else {
            for (char c = 'a'; c <= 'z'; c++) {
                generate(length - 1, partial + c);
            }
        }
    }
}
Odpovězeno 02/08/2008 v 10:40
zdroj uživatelem

hlasů
3

Potřeboval jsem to dnes, a sice odpovědi již dané mi ukázal správným směrem tak, aby nebyly přesně to, co jsem chtěl.

Zde je implementace pomocí haldy metodu. Délka pole musí být nejméně 3 a praktických důvodů nemůže být větší než 10 nebo tak, v závislosti na tom, co chcete dělat, trpělivost a takt.

Před zadáním smyčku inicializovat Perm(1 To N)s prvním permutací, Stack(3 To N)nulami * a Levels 2**. Na konci hovoru smyčky NextPerm, která se vrátí false, když jsme hotovi.

* VB to udělá za vás.

** Můžete změnit NextPerm trochu, aby to bylo zbytečné, ale je to jasnější takhle.

Option Explicit

Function NextPerm(Perm() As Long, Stack() As Long, Level As Long) As Boolean
Dim N As Long
If Level = 2 Then
    Swap Perm(1), Perm(2)
    Level = 3
Else
    While Stack(Level) = Level - 1
        Stack(Level) = 0
        If Level = UBound(Stack) Then Exit Function
        Level = Level + 1
    Wend
    Stack(Level) = Stack(Level) + 1
    If Level And 1 Then N = 1 Else N = Stack(Level)
    Swap Perm(N), Perm(Level)
    Level = 2
End If
NextPerm = True
End Function

Sub Swap(A As Long, B As Long)
A = A Xor B
B = A Xor B
A = A Xor B
End Sub

'This is just for testing.
Private Sub Form_Paint()
Const Max = 8
Dim A(1 To Max) As Long, I As Long
Dim S(3 To Max) As Long, J As Long
Dim Test As New Collection, T As String
For I = 1 To UBound(A)
    A(I) = I
Next
Cls
ScaleLeft = 0
J = 2
Do
    If CurrentY + TextHeight("0") > ScaleHeight Then
        ScaleLeft = ScaleLeft - TextWidth(" 0 ") * (UBound(A) + 1)
        CurrentY = 0
        CurrentX = 0
    End If
    T = vbNullString
    For I = 1 To UBound(A)
        Print A(I);
        T = T & Hex(A(I))
    Next
    Print
    Test.Add Null, T
Loop While NextPerm(A, S, J)
J = 1
For I = 2 To UBound(A)
    J = J * I
Next
If J <> Test.Count Then Stop
End Sub

Jiné metody jsou popsané různými autory. Knuth popisuje dva, jeden dává lexikální pořadí, ale je složitá a pomalá, druhý je známý jako metoda hladkých změn. Jie Gao a Dianjun Wang také napsal zajímavý referát.

Odpovězeno 02/10/2011 v 10:13
zdroj uživatelem

hlasů
2

Zde je odkaz, který popisuje, jak vytisknout permutace řetězce. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Odpovězeno 13/02/2014 v 22:08
zdroj uživatelem

hlasů
2

Tento kód v pythonu, při volání s allowed_charactersnastaveným na [0,1]a 4 max charakter, by přineslo 2 ^ 4 výsledky:

['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111']

def generate_permutations(chars = 4) :

#modify if in need!
    allowed_chars = [
        '0',
        '1',
    ]

    status = []
    for tmp in range(chars) :
        status.append(0)

    last_char = len(allowed_chars)

    rows = []
    for x in xrange(last_char ** chars) :
        rows.append("")
        for y in range(chars - 1 , -1, -1) :
            key = status[y]
            rows[x] = allowed_chars[key] + rows[x]

        for pos in range(chars - 1, -1, -1) :
            if(status[pos] == last_char - 1) :
                status[pos] = 0
            else :
                status[pos] += 1
                break;

    return rows

import sys


print generate_permutations()

Doufám, že to je užitečné pro vás. Pracuje s jakýmkoliv znakem, a to nejen čísla

Odpovězeno 26/05/2011 v 15:22
zdroj uživatelem

hlasů
2

Ruby:

str = "a"
100_000_000.times {puts str.next!}

Je to docela rychle, ale to bude trvat nějaký čas =). Samozřejmě, můžete začít na „AAAAAAAA“ v případě, že krátké řetězce nejsou zajímavé pro vás.

Možná jsem vyložil skutečný otázku i když - v jednom z míst, že to zní, jako jste právě potřeba, pokud si BruteForce knihovnu řetězců, ale hlavní otázka zní, jako je třeba permutate určitý řetězec.

Váš problém je poněkud podobný tomuto: http://beust.com/weblog/archives/000491.html (seznam všech celých čísel, v nichž žádná číslice se opakují, což mělo za následek spoustu jazyků to řešení, přičemž ocaml muž pomocí permutací, a některé java muž pomocí ještě jiné řešení).

Odpovězeno 15/09/2008 v 18:32
zdroj uživatelem

hlasů
0

Možné řetězec obměny mohou být vypočteny použitím rekurzivní funkce. Níže je jedním z možných řešení.

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList<String> getPerm(String s, int index) {
        ArrayList<String> perm = new ArrayList<String>();

        if (index == s.length()-1) {
            perm.add(String.valueOf(s.charAt(index)));
            return perm;
        }

        ArrayList<String> p = getPerm(s, index+1);
        char c = s.charAt(index);

        for(String pp : p) {
            for (int idx=0; idx<pp.length()+1; idx++) {
                String ss = insertCharAt(pp, idx, c);
                perm.add(ss);
            }
        }

        return perm;    
}

public static void testGetPerm(String s) {
        ArrayList<String> perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}
Odpovězeno 06/02/2017 v 06:00
zdroj uživatelem

hlasů
0

kód napsaný pro jazyka Java:

balíček namo.algorithms;

import java.util.Scanner;

public class Permuations {

public static int totalPermutationsCount = 0;
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("input string : ");
        String inputString = sc.nextLine();
        System.out.println("given input String ==> "+inputString+ " :: length is = "+inputString.length());
        findPermuationsOfString(-1, inputString);
        System.out.println("**************************************");
        System.out.println("total permutation strings ==> "+totalPermutationsCount);
    }


    public  static void findPermuationsOfString(int fixedIndex, String inputString) {
        int currentIndex = fixedIndex +1;

        for (int i = currentIndex; i < inputString.length(); i++) {
            //swap elements and call the findPermuationsOfString()

            char[] carr = inputString.toCharArray();
            char tmp = carr[currentIndex];
            carr[currentIndex] = carr[i];
            carr[i] = tmp;
            inputString =  new String(carr);

            //System.out.println("chat At : current String ==> "+inputString.charAt(currentIndex));
            if(currentIndex == inputString.length()-1) {
                totalPermutationsCount++;
                System.out.println("permuation string ==> "+inputString);
            } else {
                //System.out.println("in else block>>>>");
                findPermuationsOfString(currentIndex, inputString);
                 char[] rarr = inputString.toCharArray();
                    char rtmp = carr[i];
                    carr[i] = carr[currentIndex];
                    carr[currentIndex] = rtmp;
                    inputString =  new String(carr);
            }
        }
    }

}

Odpovězeno 05/06/2016 v 08:42
zdroj uživatelem

hlasů
0

Tak tady je elegantní, nerekurzivní, O (n!) Roztok:

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }
Odpovězeno 27/06/2015 v 08:44
zdroj uživatelem

hlasů
0

Pythonic řešení:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Odpovězeno 13/07/2014 v 08:51
zdroj uživatelem

hlasů
0
def permutation(str)
  posibilities = []
  str.split('').each do |char|
    if posibilities.size == 0
      posibilities[0] = char.downcase
      posibilities[1] = char.upcase
    else
      posibilities_count = posibilities.length
      posibilities = posibilities + posibilities
      posibilities_count.times do |i|
        posibilities[i] += char.downcase
        posibilities[i+posibilities_count] += char.upcase
      end
    end
  end
  posibilities
end

Tady je můj pohled na non rekurzivní verzi

Odpovězeno 23/01/2014 v 04:28
zdroj uživatelem

hlasů
0

Rekurzivní řešení s řidičem main()metodou.

public class AllPermutationsOfString {
public static void stringPermutations(String newstring, String remaining) {
    if(remaining.length()==0)
        System.out.println(newstring);

    for(int i=0; i<remaining.length(); i++) {
        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
        stringPermutations(newstring+remaining.charAt(i), newRemaining);
    }
}

public static void main(String[] args) {
    String string = "abc";
    AllPermutationsOfString.stringPermutations("", string); 
}

}

Odpovězeno 19/10/2013 v 02:34
zdroj uživatelem

hlasů
0
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
    list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list 

def func( x,i,j ): #returns x[i..j]
z = '' 
for i in range(i,j+1):
    z = z+x[i]
return z 

def perm( x , length , list ): #perm function
if length == 1 : # base case
    list.append( x[len(x)-1] )
    return list 
else:
    lists = perm( x , length-1 ,list )
    lists_temp = lists #temporarily storing the list 
    lists = []
    for i in range( len(lists_temp) ) :
        list_temp = gen(lists_temp[i],x[length-2],lists)
        lists += list_temp 
    return lists
Odpovězeno 22/08/2013 v 18:51
zdroj uživatelem

hlasů
0

Rekurzivní roztok v pythonu. Dobrou věc, o tento kód je to, že vyváží slovníku, s klíči jako struny a všech možných permutací jako hodnoty. Všechny možné délky řetězec jsou zahrnuty, takže ve skutečnosti vytváříte podmnožinou.

Pokud si vyžadují pouze konečné permutací, můžete odstranit další klíče ze slovníku.

V tomto kódu, slovník permutací je globální.

U základního scénáře, jsem uložit hodnotu jako obě možnosti v seznamu. perms['ab'] = ['ab','ba'],

Pro vyšší délek řetězec, funkce se týká nižších délek řetězce a zahrnuje dříve vypočtené permutací.

Funkce dělá dvě věci:

  • volá sebe s menším řetězci
  • vrátí seznam permutací konkrétního řetězce, pokud jsou již k dispozici. Pokud by se vrátila k sobě, budou tyto být použity k připojit k charakteru a vytvářejí novější permutace.

Drahé, na paměti.

perms = {}
def perm(input_string):
    global perms
    if input_string in perms:
        return perms[input_string] # This will send a list of all permutations
    elif len(input_string) == 2:
        perms[input_string] = [input_string, input_string[-1] + input_string [-2]]
        return perms[input_string]
    else:
        perms[input_string] = []
        for index in range(0, len(input_string)):
            new_string = input_string[0:index] + input_string[index +1:]
            perm(new_string)
            for entries in perms[new_string]:
                perms[input_string].append(input_string[index] + entries)
    return perms[input_string]
Odpovězeno 05/07/2013 v 05:15
zdroj uživatelem

hlasů
0

Tam je iterativní implementace Java v UncommonsMaths (pracuje pro seznam objektů):

/**
 * Generate the indices into the elements array for the next permutation. The
 * algorithm is from Kenneth H. Rosen, Discrete Mathematics and its 
 * Applications, 2nd edition (NY: McGraw-Hill, 1991), p. 284)
 */
private void generateNextPermutationIndices()
{
    if (remainingPermutations == 0)
    {
        throw new IllegalStateException("There are no permutations " +
             "remaining. Generator must be reset to continue using.");
    }
    else if (remainingPermutations < totalPermutations)
    {
        // Find largest index j with 
        // permutationIndices[j] < permutationIndices[j + 1]
        int j = permutationIndices.length - 2;
        while (permutationIndices[j] > permutationIndices[j + 1])
        {
            j--;
        }

        // Find index k such that permutationIndices[k] is smallest integer 
        // greater than permutationIndices[j] to the right
        // of permutationIndices[j].
        int k = permutationIndices.length - 1;
        while (permutationIndices[j] > permutationIndices[k])
        {
            k--;
        }

        // Interchange permutation indices.
        int temp = permutationIndices[k];
        permutationIndices[k] = permutationIndices[j];
        permutationIndices[j] = temp;

        // Put tail end of permutation after jth position in increasing order.
        int r = permutationIndices.length - 1;
        int s = j + 1;

        while (r > s)
        {
            temp = permutationIndices[s];
            permutationIndices[s] = permutationIndices[r];
            permutationIndices[r] = temp;
            r--;
            s++;
        }
    }
    --remainingPermutations;
}

/**
 * Generate the next permutation and return a list containing
 * the elements in the appropriate order.  This overloaded method
 * allows the caller to provide a list that will be used and returned.
 * The purpose of this is to improve performance when iterating over
 * permutations.  If the {@link #nextPermutationAsList()} method is
 * used it will create a new list every time.  When iterating over
 * permutations this will result in lots of short-lived objects that
 * have to be garbage collected.  This method allows a single list
 * instance to be reused in such circumstances.
 * @param destination Provides a list to use to create the
 * permutation.  This is the list that will be returned, once
 * it has been filled with the elements in the appropriate order.
 * @return The next permutation as a list.
 */
public List<T> nextPermutationAsList(List<T> destination)
{
    generateNextPermutationIndices();
    // Generate actual permutation.
    destination.clear();
    for (int i : permutationIndices)
    {
        destination.add(elements[i]);
    }
    return destination;
}

Plný zdrojový

Odpovězeno 07/05/2013 v 02:18
zdroj uživatelem

hlasů
0

c # iterativní:

public List<string> Permutations(char[] chars)
    {
        List<string> words = new List<string>();
        words.Add(chars[0].ToString());
        for (int i = 1; i < chars.Length; ++i)
        {
            int currLen = words.Count;
            for (int j = 0; j < currLen; ++j)
            {
                var w = words[j];
                for (int k = 0; k <= w.Length; ++k)
                {
                    var nstr = w.Insert(k, chars[i].ToString());
                    if (k == 0)
                        words[j] = nstr;
                    else
                        words.Add(nstr);
                }
            }
        }
        return words;
    }
Odpovězeno 26/07/2012 v 16:20
zdroj uživatelem

hlasů
0

I když to není odpověď na vaši otázku přesně, tady je jeden způsob, jak generovat každý permutace dopisů z několika řetězců stejné délky: například, pokud vaše slova „káva“, „Joomla“ a „moodle“, můžete očekáváme výstup jako "coodle", "joodee", "joffle", atd.

Zjednodušeně řečeno, počet kombinací je (počet slov) k síle (počet písmen na slovo). Takže, vyberte náhodné číslo mezi 0 a počet kombinací - 1, převést toto číslo na základnu (počet slov), pak použijte jednotlivé číslice tohoto čísla jako indikátor pro které slovo učinit další dopis od.

například: ve výše uvedeném příkladu. 3 slova, 6 písmeny = 729 kombinací. Zvolit náhodné číslo: 465. Převod na základnu 3: 122020. Vezměte první dopis od slova 1, 2. od slova 2, 3. od slova 2, 4. od slova 0 ... a dostanete ... „joofle“.

Pokud byste chtěli všechny obměny, jen smyčku od 0 do 728. Je samozřejmé, že jste právě rozhodli, jestli jednu náhodnou hodnotu, mnohem jednodušší méně matoucí způsob, jak by se smyčkou přes dopisy. Tato metoda umožňuje vyhnout se rekurzi, měli byste chtít všechny permutace, a navíc to dělá vypadat víte Maths (TM) !

V případě, že počet kombinací je příliš vysoká, můžete zlomit to do řady menších slov a spojovat je u konce.

Odpovězeno 16/09/2008 v 06:33
zdroj uživatelem

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more