bir dize tüm olası permütasyon listesini oluşturun

oy
143

Nasıl karakterlerin değişken listesini içeren, uzunluğu x ve y karakter arasında bir dize tüm olası permütasyon listesini oluşturma hakkında gider.

Herhangi bir dil çalışacak, ancak taşınabilir olmalıdır.

Oluştur 02/08/2008 saat 07:57
kaynak kullanıcı
Diğer dillerde...                            


35 cevaplar

oy
67

Bunu yapmanın birkaç yolu vardır. Sık kullanılan yöntemler Özyinelemeyi, Memoization veya dinamik programlama kullanın. Temel fikir, son yineleme üretilen tüm dizeleri, tek tek dizede her karakter ile birleştirilmiş bu dizeyi eklemek için, sonra her tekrarında, uzunluk 1 tüm dizeleri listesini üretmek olmasıdır. (Kodda değişken endeksi aşağıdaki son başlangıcında ve sonraki yineleme izler)

Bazı yalancı kod:

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)

Eğer o zaman listedeki ilk (x-1) * len (originalString) girişleri olacak, uzunluğu x değerinden bütün dizeleri az kaldırmak gerekiyordu.

Cevap 02/08/2008 saat 08:48
kaynak kullanıcı

oy
35

Bu geriye gidilmiştir kullanmak daha iyidir

#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;
}
Cevap 10/01/2012 saat 19:00
kaynak kullanıcı

oy
24

Sen bu kesin, dizeleri bir sürü almak için gidiyoruz ...

\ sum_ {i = x} ^ y {\ frac {R!} {{(n)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% % 20 7B% 20% 5Cfrac% 7Br% 7D% 7B (ri)% 7B% 7D% 7D% 20% 7D!
x ve y onları tanımlamak ve r biz seçerek olan karakter sayısıdır nasıl, - -eğer seni doğru anlama ediyorum. Kesinlikle gerektiğinde bu üretmek ve özensiz olsun ve de ki, bir POWERSET oluşturmak ve daha sonra dizeleri uzunluğunu filtre olmamalıdır.

Kesinlikle aşağıdaki bunlar oluşturmak için en iyi yol değildir, ancak bir yana, yok-az bir ilginç.

Knuth (cilt 4, fasikül 2, 7.2.1.3) (s, t) -combination + 1 şeyler s eşdeğer tekrarlama ile bir anda t alınmış olduğunu söyler - bir (s, t) -combination gösterim tarafından kullanılan eşittir Knuth {t \ tercih {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . İlk ikili biçimde her bir (s, t) -combination üreterek bu anlamaya (böylece, uzunluk (s + t)) ve her birinin 1 solundaki 0 's sayısının sayılması.

10001000011101 -> permütasyon olur: {0, 3, 4, 4, 4, 1}

Cevap 05/08/2008 saat 05:57
kaynak kullanıcı

oy
14

Knuth, Python örneğe göre Olmayan özyinelemeli çözüm:

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)
Cevap 09/11/2010 saat 14:58
kaynak kullanıcı

oy
12

Burada iyi yanıtlar bir yeri vardır. Ayrıca C ++ çok basit özyinelemeli çözüm önermek.

#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;
    });
}

Not : Tekrarlanan karakterler ile dizeleri benzersiz permütasyon üretmez.

Cevap 08/01/2014 saat 12:00
kaynak kullanıcı

oy
12

İşte C # basit bir çözümdür.

Verilen bir dize sadece farklı permütasyon üretir.

    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;
        }
    }
Cevap 05/07/2010 saat 10:06
kaynak kullanıcı

oy
12

Dayalı bazı çalışma Java kodu Sarp cevabı :

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);
    }
}
Cevap 04/04/2010 saat 19:18
kaynak kullanıcı

oy
12

Sen "de görünebilir verimli bir dizisi alt gruplarının numaralandırılıyor istediğini kısmını yapmak için bir algoritma tanımlamaktadır," - hızlı y uzunluk x N karakterlerin tüm alt kümelerini oluşturur. Bu C'de bir uygulamasını içeren

Her alt kümesi için, hala tüm permütasyon üretmek zorundayız. Örneğin eğer, bu algoritma "abc" Teşekkür verecekti, "abd", "Abe" ... ama "acb", "bac" almak için her biri sırasını değiştirmek amacıyla olurdu "abcde" dan 3 karakter istedik "bca" vb

Cevap 14/11/2008 saat 20:36
kaynak kullanıcı

oy
8

Sadece Ruby hızlı bu kadar çırpılmış:

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

permütasyon tipi yerleşik işlev için sen dil API içine görünebilir ve siz daha iyileştirilmiş kod yazmak mümkün olabilir, ama sayılar o kadar yüksek olursa, etrafa sonuçların çok olan bir çok yolu vardır emin değilim .

Neyse, kod arkasındaki fikir Z tekrarında geçerli boyutu nedeniyle, verilecek Z uzunluğunun tüm dizeleri izlemek 0 uzunluğunda dize ile başlamaktır. Sonra, her dize geçmesi ve her dize üzerine her karakter eklenir. Son olarak sonunda x eşiğinin altında olduğu bir kaldırma sonucu döndürür.

Potansiyel olarak anlamsız girişi (boş karakter listesi, x ve y'nin garip değerleri, vs.) ile test değildi.

Cevap 02/08/2008 saat 08:56
kaynak kullanıcı

oy
7

işleri Yakut cevap:

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")
Cevap 20/04/2012 saat 01:21
kaynak kullanıcı

oy
7

permute (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [( * B C), (Cı- B * )] -> [( * Bir BC ), (B A C), (M.Ö. A * ), ( * bir CB), (C A B), (CB A * önceki dize aynı alfabe ile biterse görmek için her alfabe çeki eklerken)] yinelemeleri kaldırmak için (neden? -Egzersiz)

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;
}

Baskılar tüm permütasyon sans çiftleri

Cevap 22/02/2011 saat 19:45
kaynak kullanıcı

oy
7

... ve burada C sürümü:

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;
}
Cevap 07/02/2011 saat 22:56
kaynak kullanıcı

oy
7

Eğer küçük alfabesi kendinizi kısıtlamak istiyorsanız Perl yılında, bunu yapabilirsiniz:

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

Bu küçük harflerle 1 ile 4 karakter arasında olası tüm dizeleri verir. Büyük harf için, değiştirmek "a"için "A"ve "zzzz"için "ZZZZ".

Karışık durum için çok daha zor ve böyle Perl'in yerleşik operatörler biriyle muhtemelen yapılabilir değil alır.

Cevap 15/02/2009 saat 11:02
kaynak kullanıcı

oy
7

İşte basit bir kelime C # özyinelemeli çözümdür:

Yöntem:

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;
        }

Arayan:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
Cevap 20/10/2008 saat 01:17
kaynak kullanıcı

oy
7

C özyinelemeli çözelti ++

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;
            }
        }
}
Cevap 29/09/2008 saat 02:34
kaynak kullanıcı

oy
7

Bu Common Lisp içine Ahmet'in Yakut sürümünün bir çeviri şöyledir:

(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)))))

Ve başka versiyonu, biraz daha kısa ve daha döngü tesis özelliklerini kullanarak:

(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)))))
Cevap 16/09/2008 saat 06:15
kaynak kullanıcı

oy
6

Aşağıdaki Java özyineleme baskılar belirli bir dizeye tüm permütasyon:

//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 yapar yukarıdaki "PERMUT" yönteminin güncellenmiş sürümü aşağıdadır! Yukarıdaki yönteme göre daha az tekrarlanan aramalara (n faktöryel)

//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()));
   }
}
Cevap 19/06/2013 saat 05:23
kaynak kullanıcı

oy
5

İşte javascript, ile geldi olmayan bir özyinelemeli versiyonu. o eleman takas bazı benzerlikler olmasına rağmen O, yukarıda Knuth'un özyinesiz birine dayanarak değil. Ben en fazla 8 elementlerin giriş diziler için doğru olup olmadığını doğruladık.

Hızlı bir optimizasyon ön yayınını olacağını outdizi ve kaçınarak push().

Temel fikir:

  1. Tek bir kaynak dizi göz önüne alındığında, bu da, her bir zaman soğukkanlı diğer unsurları terk eden her bir alt öğe ile birinci elemanı değiş tokuş dizileri bir birinci yeni bir grup oluşturur. Örneğin: 1234 göz önüne alındığında, 1234, 2134, 3214, 4231 üretir.

  2. Yeni bir geçiş için tohum olarak önceki geçişte her dizi kullanarak, ancak bunun yerine birinci eleman takas, takip eden her elemanı ile ikinci elemanı değiş tokuş. Ayrıca, bu kez, çıktıda orijinal dizi içermez.

  3. yapılan dek 2. adımı tekrarlayın.

İşte kod örnektir:

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;
}
Cevap 03/08/2011 saat 08:11
kaynak kullanıcı

oy
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;
    }
}
Cevap 24/10/2010 saat 23:01
kaynak kullanıcı

oy
4

Ben ilk etapta bunu yapmak istiyor neden emin değilim. x ve y herhangi orta büyük değerleri için elde edilen dizi büyük olacaktır ve x gibi katlanarak büyür ve / veya y büyük olacaktır.

Eğer iktidara yani 11,881,376 (26 alırsınız olası karakter set alfabenin 26 küçük harf söylemek ve uzunluğu = 5. bellek tükendi yok varsayarsak tüm permütasyon oluşturmak için başvurunuzu soralım geri 5) dizeleri. 6 o uzunluk kadar Bump ve 308.915.776 dizeleri geri döneceğiz. Bu numaralar acı büyük, çok hızlı bir şekilde olsun.

İşte Java araya bir çözüm. Sen (x ve y karşılık gelir) iki çalışma zamanı argümanlar sunmanız gerekir. İyi eğlenceler.

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);
            }
        }
    }
}
Cevap 02/08/2008 saat 10:40
kaynak kullanıcı

oy
3

Bu bugün ihtiyacı vardı ve zaten verilen cevaplar bana doğru yönde işaret rağmen, onlar istediğim oldukça ne idi.

İşte yığın yöntemi kullanılarak bir uygulama bu. Dizinin uzunluğu en az 3 ve pratik hususlar için olmayacak olmalıdır den büyük 10 ya da öylesine, sen sabır ve saat hızını yapmak istediğinize bağlı.

Eğer döngü girmeden önce initialize Perm(1 To N), ilk permütasyon ile Stack(3 To N)* ve sıfır ile Levelbirlikte 2**. Döngü çağrısı sonunda NextPerm, bitince, return false hangi.

* VB sizin için yapacak.

** Sen NextPerm bu gereksiz hale getirmek için biraz değiştirebilir, ama böyle daha açık.

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

Diğer yöntemler, çeşitli yazarlar tarafından açıklanmıştır. Knuth diğer düz değişikliklerin yöntemi olarak bilinir, bir sözcük sırasını verir, ancak karmaşık ve yavaş, iki açıklar. Jie Gao ve Dianjun Wang da ilginç bir kağıt yazdı.

Cevap 02/10/2011 saat 10:13
kaynak kullanıcı

oy
2

İşte bir dizenin permütasyon yazdırmak açıklamaktadır bir bağlantıdır. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Cevap 13/02/2014 saat 22:08
kaynak kullanıcı

oy
2

Python Bu kod ile çağrıldığında allowed_charactersiçin sette [0,1]ve 4 karakter max, 2 ^ 4 sonuç üretecektir:

['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()

bu sizin için faydalı olduğunu umuyoruz. herhangi bir karakter, sadece numaraları ile çalışır

Cevap 26/05/2011 saat 15:22
kaynak kullanıcı

oy
2

nil:

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

Oldukça hızlı, ama) = biraz zaman alacak. kısa dizeleri size ilginç değilse Tabii ki, "aaaaaaaa" başlayabilir.

Eğer sadece dizeleri bir kaba kuvvet kütüphanesini gerekirse olarak kulağa mesajların birinde, ancak belirli bir dize permutate gerekiyor gibi ana Söz konusu bu sesler - Yine gerçek soru yanlış olabilir.

: Senin sorunun bu bir biraz benzer http://beust.com/weblog/archives/000491.html ile, dillerin bir sürü sonuçlandı basamak hiçbiri kendilerini tekrar ettiği bütün tamsayılar, bunu çözme (listedeki permütasyon kullanarak ocaml adam ve henüz başka bir çözüm kullanarak bazı java adam).

Cevap 15/09/2008 saat 18:32
kaynak kullanıcı

oy
0

olası dize permütasyon özyinelemeli fonksiyonu kullanılarak hesaplanabilir. Aşağıda olası çözüm biridir.

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());
}
Cevap 06/02/2017 saat 06:00
kaynak kullanıcı

oy
0

java dili için yazılmıştır kod:

Paket namo.algorithms;

ithalat 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);
            }
        }
    }

}

Cevap 05/06/2016 saat 08:42
kaynak kullanıcı

oy
0

Eh burada zarif, özyinesiz, O (n!) 'Dir çözüm:

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;
    }
Cevap 27/06/2015 saat 08:44
kaynak kullanıcı

oy
0

pythonic çözüm:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Cevap 13/07/2014 saat 08:51
kaynak kullanıcı

oy
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

İşte olmayan bir özyinelemeli sürümü almak benim

Cevap 23/01/2014 saat 04:28
kaynak kullanıcı

oy
0

Sürücü ile Rekürsif Çözüm main()yöntemiyle.

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); 
}

}

Cevap 19/10/2013 saat 02:34
kaynak kullanıcı

oy
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
Cevap 22/08/2013 saat 18:51
kaynak kullanıcı

oy
0

Python bir özyinelemeli çözüm. Bu kodu hakkında iyi bir şey dizeleri olarak anahtarları ve değerleri olarak tüm olası permütasyon ile, bir sözlük ihraç olmasıdır. aslında, bir üst kümesini oluştururken böylece tüm olası dize uzunlukları dahil edilmiştir.

Yalnızca son permütasyon gerektiriyorsa, sözlükten diğer anahtarlar silebilirsiniz.

Bu kodda, permütasyon sözlüğü geneldir.

Baz durumda, ben bir listede hem olasılıklar olarak değerini depolar. perms['ab'] = ['ab','ba'].

Daha yüksek dizi uzunlukları için, fonksiyon dizisi uzunlukları alt değinmektedir ve daha önce hesaplanan permütasyon içermektedir.

Fonksiyon iki şey yapar:

  • Daha küçük bir iple kendisini çağıran
  • Zaten varsa belirli bir dize permütasyon bir listesini döndürür. kendisine dönmüş olsaydı, bu karakterin eklenecek ve yeni permütasyon oluşturmak için kullanılacaktır.

bellek için pahalı.

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]
Cevap 05/07/2013 saat 05:15
kaynak kullanıcı

oy
0

Bir iteratif bir Java uygulaması vardır UncommonsMaths (nesneler listesi için çalışır):

/**
 * 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;
}

Tam kaynak

Cevap 07/05/2013 saat 02:18
kaynak kullanıcı

oy
0

c # yinelemeli:

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;
    }
Cevap 26/07/2012 saat 16:20
kaynak kullanıcı

oy
0

Bu tam olarak sorunuza cevap vermez rağmen, burada da aynı uzunlukta bir dize bir dizi harflerin her permütasyon oluşturmak için bir yolu şudur: sözlerin "kahve", "Joomla" ve "moodle" olsaydı, örneğin, şunları yapabilirsiniz "coodle", "joodee", "joffle" vb gibi çıktı bekliyoruz

Temel olarak, kombinasyon sayısı (kelime başına harf sayısı) gücüne (kelime sayısı). sonraki mektup almak için hangi sözcük daha sonra göstergesi olarak bu sayının her rakamı kullanın (sözcük sayısını), 1 tabanına bu sayıyı dönüştürmek - Yani, 0 arasında rastgele bir sayı ve kombinasyon sayısını seçin.

örneğin: yukarıdaki örnekte. 3 kelime, 6 harf = 729 kombinasyonları. 122020. kelimesi 0 dan kelimesi 2, 4. gelen kelime 2'den 2 kelime 1, 3., ilk harfini alın ... ve sen "joofle" ... olsun: 465. dönüştürme 3 temel almak: rastgele bir sayı seçin.

Tüm permütasyon, 0'dan Tabii 728. sadece döngü isteseydim sadece tek rastgele bir değer seçerek eğer, çok daha basit , daha az kafa karıştırıcı yolu harflerin üzerinde döngü olacaktır. Bu yöntem Özyinelemeyi önlemek için, tüm permütasyon istesin sağlar, ayrıca bunu Matematik biliyormuş gibi görünmesini sağlar (tm) !

Kombinasyon sayısı çok fazla ise, daha küçük kelime bir dizi bölmek ve sonunda onları bir arada kullanabilirsiniz.

Cevap 16/09/2008 saat 06:33
kaynak kullanıcı

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