توليد قائمة من جميع التباديل الممكنة من سلسلة

Question

كيف يمكنني التوجه نحو توليد قائمة من جميع التباديل الممكنة من سلسلة بين x و y حرفا في الطول ، التي تحتوي على متغير قائمة الشخصيات.

أي لغة العمل ، ولكن يجب أن تكون محمولة.

Answer 1

هناك عدة طرق للقيام بذلك.الطرق الشائعة استخدام العودية, التحفيظ, أو البرمجة الديناميكية.والفكرة الأساسية هي أن كنت تنتج قائمة من كافة السلاسل بطول 1 ، ثم في كل التكرار ، على كافة السلاسل التي تنتج في الماضي التكرار ، إضافة إلى أن سلسلة متسلسلة مع كل حرف في السلسلة بشكل فردي.(متغير مؤشر في البرمجية أدناه بتتبع بداية من التكرار التالي)

بعض شبة الكود:

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)

ثم كنت بحاجة إلى إزالة كافة السلاسل أقل من x في طول سيكونون أول (x-1) * len(originalString) الإدخالات في القائمة.

Answer 2

فإنه من الأفضل استخدام التراجع

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

Answer 3

أنت ذاهب للحصول على الكثير من سلاسل, هذا مؤكد...

\sum_{i=x}^y{\فارك{r!}{{(r-i)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey%20%7B%20%5Cfrac%7Br!%7D%7B%7B(r-i)%7D!%7D%20%7D
حيث x و y هو كيف تحدد لهم و r هو عدد الأحرف التي يتم اختيار من ... لو أنا فهمتك بشكل صحيح.بالتأكيد يجب أن تولد هذه حسب الحاجة وليس الحصول على قذرة ويقول توليد باورسيت ثم تصفية طول السلاسل.

التالية هي بالتأكيد ليست أفضل طريقة لتوليد هذه, لكنه مثيرة للاهتمام جانبا ، لا شيء بين بين فإن أقل.

كانوث (المجلد 4, مجلد 2, 7.2.1.3) يخبرنا أن (s,t)-الجمع هو ما يعادل s+1 من الأمور التي تؤخذ t في كل مرة مع التكرار-وهو (s,t)-الجمع الرموز المستخدمة من قبل كانوث يساوي {t \اختيار {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.يمكننا معرفة ذلك عن طريق توليد الأولى كل (s,t)-الجمع في شكل ثنائي (لذا ، من طول (s+t)) و عد عدد من 0 إلى يمين كل من 1.

10001000011101 --> يصبح التقليب:{0, 3, 4, 4, 4, 1}

Answer 4

غير متكررة الحل وفقا كانوث ، بيثون على سبيل المثال:

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)

Answer 5

كنت قد ننظر في "بكفاءة تعداد مجموعات فرعية من مجموعة"،الذي يصف خوارزمية أن تفعل ما تريد - بسرعة إنشاء مجموعات فرعية من الأحرف ن من طول x إلى y.أنه يحتوي على التنفيذ في C.

لكل فرعية, كنت لا تزال لديها لتوليد جميع التباديل.على سبيل المثال إذا أردت 3 شخصيات من "abcde", هذه الخوارزمية سوف تعطيك "اي بي سي" ، "عبد", "آبي"...ولكن عليك بدل ترتيب كذا كل واحد للحصول على "acb", "باك", "bca" ، الخ.

Answer 6

بعض العامل كود جافا على أساس سارب الجواب:

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

Answer 7

هنا حل بسيط في C#.

فإنه يولد سوى متميزة التباديل من سلسلة معينة.

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

Answer 8

هناك الكثير من إجابات جيدة هنا.وأقترح أيضا بسيط جدا متكررة حل في 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;
    });
}

ملاحظة:سلاسل مع الأحرف المتكررة لن تنتج فريدة من نوعها التباديل.

Answer 9

أنا فقط جلد هذا الأمر سريعا في روبي:

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

قد ننظر إلى اللغة API بنيت في التقليب نوع الوظائف, كنت قد تكون قادرة على كتابة المزيد من رمز الأمثل ، ولكن إذا كانت الأرقام مرتفعة, أنا لست متأكد من أن هناك كثيرا من طريقة حول وجود الكثير من النتائج.

على أي حال, الفكرة من وراء رمز تبدأ مع سلسلة من طول 0 ، ثم تتبع كل الخيوط من طول Z حيث Z هو الحجم الحالي في التكرار.ثم تذهب من خلال كل سلسلة و إلحاق كل حرف على كل سلسلة.أخيرا في النهاية ، وإزالة أي التي كانت تحت x عتبة العودة في النتيجة.

لم أكن اختبار يحتمل معنى الإدخال (حرف خالية قائمة غريب قيم x و y ، إلخ).

Answer 10

هذه ترجمة مايك روبي نسخة إلى 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)))))

و آخر نسخة أقصر قليلا و باستخدام أكثر من حلقة مرفق الميزات:

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

Answer 11

هنا هي كلمة بسيطة C# العودية الحل:

الطريقة:

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

الدعوة:

string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);

Answer 12

في بيرل, إذا كنت تريد أن تحد نفسك إلى أحرف صغيرة الأبجدية ، يمكنك القيام بذلك:

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

وهذا يعطي كل شيء ممكن السلاسل بين 1 و 4 شخصيات استخدام أحرف صغيرة.عن الأحرف الكبيرة, تغيير "a" إلى "A" و "zzzz" إلى "ZZZZ".

المختلطة الحالة يصبح الأمر أصعب بكثير ، وربما غير قابلة للتنفيذ مع واحد Perl مدمج شركات مثل ذلك.

Answer 13

...و هنا هو 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;
}

Answer 14

بدل ترتيب كذا (ABC) -> A. بيرم(BC) -> A. بيرم[B. بيرم(ج)] -> A. بيرم[(*بج) (Cب*)] -> [(*Aقبل الميلاد) ، (بAج), (BCA*), (*ACB) و (جAب) (CBA*)] لإزالة التكرارات عند إدراج كل الحروف الأبجدية تحقق لمعرفة ما إذا كان السابق سلسلة ينتهي مع نفس الأبجدية (لماذا ؟ -ممارسة الرياضة)

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

طباعة جميع التباديل بلا التكرارات

Answer 15

روبي الجواب أن يعمل:

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

Answer 16

عودي حل في 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;
            }
        }
}

Answer 17

التالية جافا العودية يطبع جميع التباديل من سلسلة معينة:

//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!(ن مضروب) أقل دعوات متكررة مقارنة مع الطريقة المذكورة أعلاه

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

Answer 18

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

Answer 19

وهنا غير متكررة النسخة خطرت في جافا سكريبت.ليس على أساس كانوث غير متكررة واحدة فوق ، على الرغم من أنها لديها بعض أوجه التشابه في عنصر مبادلة.لقد تم التحقق من صحة الإدخال المصفوفات تصل إلى 8 عناصر.

سريع الأمثل أن يكون قبل flighting على out مجموعة وتجنب push().

الفكرة الأساسية هي:

1. بالنظر إلى مصدر واحد مجموعة توليد أول مجموعة جديدة من المصفوفات التي مبادلة العنصر الأول مع بعضها لاحقا عنصر في المقابل ، في كل مرة يترك العناصر الأخرى رابط الجأش.على سبيل المثال:نظرا 1234 ، وتوليد 1234, 2134, 3214, 4231.

2. استخدام كل مجموعة من السابق تمرير مثل البذور الجديدة تمر ، ولكن بدلا من مبادلة العنصر الأول ، المبادلة العنصر الثاني مع بعضها لاحقا عنصر.أيضا, هذه المرة, لا تشمل مجموعة أصلية في الإخراج.

3. كرر الخطوة 2 حتى القيام به.

هنا هو نموذج التعليمات البرمجية:

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

Answer 20

لست متأكدا لماذا كنت تريد أن تفعل هذا في المقام الأول.مما أدى تعيين أي معتدل كبيرة قيم x و y سوف تكون ضخمة ، سوف تنمو باطراد x أو y الحصول على أكبر.

دعونا نقول لديك مجموعة من الشخصيات المحتملة هو 26 صغيرة الحروف الأبجدية ، و تسأل التطبيق الخاص بك لتوليد جميع التباديل حيث الطول = 5.على افتراض أنك لا ينفد من الذاكرة سوف تحصل على 11,881,376 (أي26 إلى قوة 5) سلاسل مرة أخرى.عثرة أن طول يصل إلى 6 ، و ستحصل على 308,915,776 السلاسل مرة أخرى.هذه الأرقام على نحو مؤلم كبيرة جدا بسرعة.

هنا الحل لقد وضعت في جاوة.سوف تحتاج إلى تقديم اثنين من الحجج وقت (المقابلة x و y).يكون متعة.

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

Answer 21

أنا بحاجة إلى هذا اليوم ، على الرغم من أن الإجابات سبق وأشار لي في الاتجاه الصحيح أنها لم تكن تماما ما أردت.

وهنا التنفيذ باستخدام كومة الأسلوب.طول المصفوفة يجب أن تكون على الأقل 3 و الاعتبارات العملية لا تكون أكبر من 10 أو نحو ذلك ، اعتمادا على ما تريد القيام به والصبر على مدار الساعة السرعة.

قبل أن تدخل حلقة ، التهيئة Perm(1 To N) مع التقليب ، Stack(3 To N) مع أصفار* ، Level مع 2**.في نهاية حلقة الاتصال NextPerm, والتي سوف return false عندما ننتهي.

* VB سوف نفعل ذلك لك.

** يمكنك تغيير NextPerm قليلا لجعل هذا لا لزوم لها, لكنه أكثر وضوحا مثل هذا.

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

أساليب أخرى تم وصفها من قبل مختلف الكتاب.كانوث يصف اثنان, واحد يعطي المعجمية النظام ، ولكن معقدة وبطيئة ، وغيرها كما هو معروف في الأسلوب العادي التغييرات.جي غاو Dianjun وانغ أيضا كتب ورقة مثيرة للاهتمام.

Answer 22

في روبي:

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

فهي سريعة جدا ، ولكن ذلك سوف يستغرق بعض الوقت =).بالطبع, يمكنك أن تبدأ في "aaaaaaaa" إذا كانت قصيرة السلاسل ليست مثيرة للاهتمام بالنسبة لك.

أنا قد أسأت فهم السؤال الفعلي على الرغم من ذلك - في واحدة من المشاركات بدا الأمر كما لو كنت فقط بحاجة bruteforce مكتبة السلاسل ، ولكن في السؤال الرئيسي يبدو أنك تحتاج إلى permutate سلسلة معينة.

مشكلتك هي تشبه إلى حد ما هذا واحد: http://beust.com/weblog/archives/000491.html (قائمة جميع الأعداد الصحيحة في أي من أرقام تكرر نفسها ، مما أدى إلى الكثير من اللغات حلها ، مع ocaml الرجل باستخدام التباديل و بعض جافا الرجل باستخدام آخر حل).

Answer 23

هذا الرمز في بيثون ، عندما دعا مع allowed_characters تعيين [0,1] و 4 حرف كحد أقصى ، من شأنه أن يولد 2^4 النتائج:

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

نأمل أن يكون هذا مفيد لك.يعمل مع أي شخصية ، وليس فقط أرقام

Answer 24

هنا هو الرابط الذي يشرح كيفية طباعة التباديل من سلسلة.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Answer 25

على الرغم من أن هذا لا يجيب على سؤالك بالضبط, هنا طريقة لتوليد كل التقليب من الرسائل من عدد من سلاسل من نفس طول:على سبيل المثال, إذا كانت كلماتك "القهوة", "جملة" و "موودل" ، يمكنك أن تتوقع انتاج مثل "coodle", "joodee", "joffle" ، الخ.

في الأساس, عدد المجموعات هو (عدد الكلمات) قوة (عدد الحروف في كلمة).لذا اختيار رقم عشوائي بين 0 و عدد المجموعات - 1, تحويل هذا الرقم إلى قاعدة (عدد الكلمات) ، ثم استخدام كل رقم من هذا العدد كما هو المؤشر على أي كلمة أن تأخذ الرسالة القادمة من.

على سبيل المثال:في المثال أعلاه.الكلمات 3 ، 6 حروف = 729 مجموعات.اختيار رقم عشوائي:465.تحويل قاعدة 3:122020.خذ أول حرف من الكلمة 1 ، 2 من كلمة 2 ، 3 من كلمة 2 ، 4 من كلمة 0...و يمكنك الحصول على..."joofle".

إذا كنت تريد كل التباديل, مجرد حلقة من 0 إلى 728.بالطبع, إذا كنت اختيار واحد فقط قيمة عشوائية ، أبسط أقل مربكة كانت حلقة فوق الحروف.هذه الطريقة تمكنك من تجنب العودية ، ينبغي أن كنت تريد كل التباديل, بالإضافة إلى أنه يجعلك تبدو وكأنك تعرف الرياضيات^(tm)!

وإذا كان عدد مجموعات المفرط ، يمكنك تقسيمها إلى سلسلة من أصغر الكلمات لسلسلة لهم في النهاية.

Answer 26

c# التكرارية:

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

Answer 27

هناك تكرارية تنفيذ جافا في UncommonsMaths (يعمل للحصول على قائمة من الكائنات):

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

المصدر الكامل

Answer 28

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

Answer 29

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

هنا هو بلدي يأخذ على غير متكررة الإصدار

Answer 30

على pythonic الحل:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]