توليد قائمة من جميع التباديل الممكنة من سلسلة
-
08-06-2019 - |
سؤال
كيف يمكنني التوجه نحو توليد قائمة من جميع التباديل الممكنة من سلسلة بين x و y حرفا في الطول ، التي تحتوي على متغير قائمة الشخصيات.
أي لغة العمل ، ولكن يجب أن تكون محمولة.
المحلول
هناك عدة طرق للقيام بذلك.الطرق الشائعة استخدام العودية, التحفيظ, أو البرمجة الديناميكية.والفكرة الأساسية هي أن كنت تنتج قائمة من كافة السلاسل بطول 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) الإدخالات في القائمة.
نصائح أخرى
فإنه من الأفضل استخدام التراجع
#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;
}
أنت ذاهب للحصول على الكثير من سلاسل, هذا مؤكد...
\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}
غير متكررة الحل وفقا كانوث ، بيثون على سبيل المثال:
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)
كنت قد ننظر في "بكفاءة تعداد مجموعات فرعية من مجموعة"،الذي يصف خوارزمية أن تفعل ما تريد - بسرعة إنشاء مجموعات فرعية من الأحرف ن من طول x إلى y.أنه يحتوي على التنفيذ في C.
لكل فرعية, كنت لا تزال لديها لتوليد جميع التباديل.على سبيل المثال إذا أردت 3 شخصيات من "abcde", هذه الخوارزمية سوف تعطيك "اي بي سي" ، "عبد", "آبي"...ولكن عليك بدل ترتيب كذا كل واحد للحصول على "acb", "باك", "bca" ، الخ.
بعض العامل كود جافا على أساس سارب الجواب:
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);
}
}
هنا حل بسيط في 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;
}
}
هناك الكثير من إجابات جيدة هنا.وأقترح أيضا بسيط جدا متكررة حل في 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;
});
}
ملاحظة:سلاسل مع الأحرف المتكررة لن تنتج فريدة من نوعها التباديل.
أنا فقط جلد هذا الأمر سريعا في روبي:
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 ، إلخ).
هذه ترجمة مايك روبي نسخة إلى 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)))))
هنا هي كلمة بسيطة 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);
في بيرل, إذا كنت تريد أن تحد نفسك إلى أحرف صغيرة الأبجدية ، يمكنك القيام بذلك:
my @result = ("a" .. "zzzz");
وهذا يعطي كل شيء ممكن السلاسل بين 1 و 4 شخصيات استخدام أحرف صغيرة.عن الأحرف الكبيرة, تغيير "a"
إلى "A"
و "zzzz"
إلى "ZZZZ"
.
المختلطة الحالة يصبح الأمر أصعب بكثير ، وربما غير قابلة للتنفيذ مع واحد Perl مدمج شركات مثل ذلك.
...و هنا هو 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;
}
بدل ترتيب كذا (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;
}
طباعة جميع التباديل بلا التكرارات
روبي الجواب أن يعمل:
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")
عودي حل في 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;
}
}
}
التالية جافا العودية يطبع جميع التباديل من سلسلة معينة:
//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()));
}
}
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;
}
}
وهنا غير متكررة النسخة خطرت في جافا سكريبت.ليس على أساس كانوث غير متكررة واحدة فوق ، على الرغم من أنها لديها بعض أوجه التشابه في عنصر مبادلة.لقد تم التحقق من صحة الإدخال المصفوفات تصل إلى 8 عناصر.
سريع الأمثل أن يكون قبل flighting على out
مجموعة وتجنب push()
.
الفكرة الأساسية هي:
بالنظر إلى مصدر واحد مجموعة توليد أول مجموعة جديدة من المصفوفات التي مبادلة العنصر الأول مع بعضها لاحقا عنصر في المقابل ، في كل مرة يترك العناصر الأخرى رابط الجأش.على سبيل المثال:نظرا 1234 ، وتوليد 1234, 2134, 3214, 4231.
استخدام كل مجموعة من السابق تمرير مثل البذور الجديدة تمر ، ولكن بدلا من مبادلة العنصر الأول ، المبادلة العنصر الثاني مع بعضها لاحقا عنصر.أيضا, هذه المرة, لا تشمل مجموعة أصلية في الإخراج.
كرر الخطوة 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;
}
لست متأكدا لماذا كنت تريد أن تفعل هذا في المقام الأول.مما أدى تعيين أي معتدل كبيرة قيم 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);
}
}
}
}
أنا بحاجة إلى هذا اليوم ، على الرغم من أن الإجابات سبق وأشار لي في الاتجاه الصحيح أنها لم تكن تماما ما أردت.
وهنا التنفيذ باستخدام كومة الأسلوب.طول المصفوفة يجب أن تكون على الأقل 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 وانغ أيضا كتب ورقة مثيرة للاهتمام.
في روبي:
str = "a"
100_000_000.times {puts str.next!}
فهي سريعة جدا ، ولكن ذلك سوف يستغرق بعض الوقت =).بالطبع, يمكنك أن تبدأ في "aaaaaaaa" إذا كانت قصيرة السلاسل ليست مثيرة للاهتمام بالنسبة لك.
أنا قد أسأت فهم السؤال الفعلي على الرغم من ذلك - في واحدة من المشاركات بدا الأمر كما لو كنت فقط بحاجة bruteforce مكتبة السلاسل ، ولكن في السؤال الرئيسي يبدو أنك تحتاج إلى permutate سلسلة معينة.
مشكلتك هي تشبه إلى حد ما هذا واحد: http://beust.com/weblog/archives/000491.html (قائمة جميع الأعداد الصحيحة في أي من أرقام تكرر نفسها ، مما أدى إلى الكثير من اللغات حلها ، مع ocaml الرجل باستخدام التباديل و بعض جافا الرجل باستخدام آخر حل).
هذا الرمز في بيثون ، عندما دعا مع 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()
نأمل أن يكون هذا مفيد لك.يعمل مع أي شخصية ، وليس فقط أرقام
هنا هو الرابط الذي يشرح كيفية طباعة التباديل من سلسلة.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
على الرغم من أن هذا لا يجيب على سؤالك بالضبط, هنا طريقة لتوليد كل التقليب من الرسائل من عدد من سلاسل من نفس طول:على سبيل المثال, إذا كانت كلماتك "القهوة", "جملة" و "موودل" ، يمكنك أن تتوقع انتاج مثل "coodle", "joodee", "joffle" ، الخ.
في الأساس, عدد المجموعات هو (عدد الكلمات) قوة (عدد الحروف في كلمة).لذا اختيار رقم عشوائي بين 0 و عدد المجموعات - 1, تحويل هذا الرقم إلى قاعدة (عدد الكلمات) ، ثم استخدام كل رقم من هذا العدد كما هو المؤشر على أي كلمة أن تأخذ الرسالة القادمة من.
على سبيل المثال:في المثال أعلاه.الكلمات 3 ، 6 حروف = 729 مجموعات.اختيار رقم عشوائي:465.تحويل قاعدة 3:122020.خذ أول حرف من الكلمة 1 ، 2 من كلمة 2 ، 3 من كلمة 2 ، 4 من كلمة 0...و يمكنك الحصول على..."joofle".
إذا كنت تريد كل التباديل, مجرد حلقة من 0 إلى 728.بالطبع, إذا كنت اختيار واحد فقط قيمة عشوائية ، أبسط أقل مربكة كانت حلقة فوق الحروف.هذه الطريقة تمكنك من تجنب العودية ، ينبغي أن كنت تريد كل التباديل, بالإضافة إلى أنه يجعلك تبدو وكأنك تعرف الرياضيات(tm)!
وإذا كان عدد مجموعات المفرط ، يمكنك تقسيمها إلى سلسلة من أصغر الكلمات لسلسلة لهم في النهاية.
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;
}
هناك تكرارية تنفيذ جافا في 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;
}
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
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
هنا هو بلدي يأخذ على غير متكررة الإصدار
على pythonic الحل:
from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]