Genereer lys van alle moontlike permutasies van 'n string
https://stackoverflow.com/questions/361
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianVra
Hoe sal ek te werk gaan om 'n lys van alle moontlike permutasies van 'n string tussen x en y karakters in lengte te genereer, wat 'n veranderlike lys karakters bevat.
Enige taal sal werk, maar dit moet draagbaar wees.
Oplossing
Daar is verskeie maniere om dit te doen.Algemene metodes gebruik rekursie, memorisering of dinamiese programmering.Die basiese idee is dat jy 'n lys van alle stringe van lengte 1 produseer, en dan in elke iterasie, vir alle stringe wat in die laaste iterasie geproduseer is, daardie string wat met elke karakter in die string aaneengeskakel is individueel byvoeg.(die veranderlike indeks in die kode hieronder hou tred met die begin van die laaste en die volgende iterasie)
Sommige pseudokode:
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)
jy sal dan alle stringe minder as x lank moet verwyder, dit sal die eerste (x-1) * len(originalString) inskrywings in die lys wees.
Ander wenke
Dit is beter om terugsporing te gebruik
#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;
}
Jy gaan baie snare kry, dis verseker...
\sum_{i=x}^y{\frac{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
Waar, x en y is hoe jy hulle definieer en r is die aantal karakters waaruit ons kies -- as ek jou reg verstaan.Jy moet dit beslis genereer soos nodig en nie slordig raak en sê, genereer 'n kragstel en filter dan die lengte van stringe nie.
Die volgende is beslis nie die beste manier om dit te genereer nie, maar dit is nietemin 'n interessante eenkant.
Knuth (volume 4, fascicle 2, 7.2.1.3) vertel ons dat (s,t)-kombinasie gelykstaande is aan s+1 dinge wat t op 'n slag geneem word met herhaling -- 'n (s,t)-kombinasie is notasie wat gebruik word deur Knuth wat gelyk is aan {t \choose {s+t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D.Ons kan dit uitvind deur eers elke (s,t)-kombinasie in binêre vorm (dus, van lengte (s+t)) te genereer en die aantal 0'e aan die linkerkant van elke 1 te tel.
10001000011101 --> word die permutasie:{0, 3, 4, 4, 4, 1}
Nie-rekursiewe oplossing volgens Knuth, Python-voorbeeld:
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)
Jy kan dalk kyk na "Die doeltreffende opsomming van die deelversamelings van 'n stel", wat 'n algoritme beskryf om deel te doen van wat jy wil - genereer vinnig alle substelle van N karakters van lengte x tot y.Dit bevat 'n implementering in C.
Vir elke subset sal jy steeds al die permutasies moet genereer.As jy byvoorbeeld 3 karakters van "abcde" wou hê, sou hierdie algoritme vir jou "abc","abd", "abe"...maar jy sal elkeen moet permuteer om "acb", "bac", "bca", ens.
Sommige werkende Java-kode gebaseer op Sarp se antwoord:
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);
}
}
Hier is 'n eenvoudige oplossing in C#.
Dit genereer slegs die duidelike permutasies van 'n gegewe string.
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;
}
}
Hier is baie goeie antwoorde.Ek stel ook 'n baie eenvoudige rekursiewe oplossing in C++ voor.
#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;
});
}
Let wel:snare met herhaalde karakters sal nie unieke permutasies produseer nie.
Ek het dit net vinnig in Ruby opgetel:
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
Jy kan dalk na taal-API kyk vir ingeboude permutasietipe funksies, en jy kan dalk meer geoptimaliseerde kode skryf, maar as die getalle so hoog is, is ek nie seker daar is veel van 'n manier om baie resultate te kry nie. .
In elk geval, die idee agter die kode is om te begin met 'n string van lengte 0, hou dan tred met al die stringe van lengte Z waar Z die huidige grootte in die iterasie is.Gaan dan deur elke string en voeg elke karakter by elke string.Verwyder uiteindelik aan die einde enige wat onder die x-drempel was en gee die resultaat terug.
Ek het dit nie getoets met potensieel betekenislose invoer nie (nul karakterlys, vreemde waardes van x en y, ens.).
Dit is 'n vertaling van Mike se Ruby-weergawe in 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)))))
En nog 'n weergawe, effens korter en met meer lusfasiliteiteienskappe:
(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)))))
Hier is 'n eenvoudige woord C# rekursiewe oplossing:
Metode:
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;
}
Bel:
string[] letters = new string[]{"a","b","c"};
ArrayList words = CalculateWordPermutations(letters, new ArrayList(), 0);
In Perl, as jy jouself tot die kleinletter alfabet wil beperk, kan jy dit doen:
my @result = ("a" .. "zzzz");
Dit gee alle moontlike stringe tussen 1 en 4 karakters deur kleinletters te gebruik.Vir hoofletters, verander "a" aan "A" en "zzzz" aan "ZZZZ".
Vir gemengde gevalle word dit baie moeiliker, en waarskynlik nie doenbaar met een van Perl se ingeboude operateurs soos dit nie.
...en hier is die C weergawe:
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;
}
permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)] Om duplikate te verwyder wanneer u elke alfabet -kontrole invoeg om te sien of die vorige string met dieselfde alfabet eindig (waarom?-oefening)
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;
}
Druk alle permutasies sonder duplikate
Ruby antwoord wat werk:
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")
Rekursiewe oplossing in 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;
}
}
}
Die volgende Java-rekursie druk alle permutasies van 'n gegewe string:
//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);
}
}
Hierna volg die opgedateerde weergawe van bogenoemde "permut" metode wat n!(n faktoriale) minder rekursiewe oproepe in vergelyking met die bogenoemde metode
//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;
}
}
Hier is 'n nie-rekursiewe weergawe waarmee ek vorendag gekom het, in javascript.Dit is nie gebaseer op Knuth se nie-rekursiewe een hierbo nie, alhoewel dit 'n paar ooreenkomste in element-uitruiling het.Ek het die korrektheid daarvan geverifieer vir invoerskikkings van tot 8 elemente.
'N vinnige optimalisering sou wees pre-flighting die out skikking en vermy push().
Die basiese idee is:
Gegewe 'n enkele bronskikking, genereer 'n eerste nuwe stel skikkings wat die eerste element om die beurt met elke daaropvolgende element omruil, elke keer wat die ander elemente ongestoord laat.bv:gegee 1234, genereer 1234, 2134, 3214, 4231.
Gebruik elke skikking van die vorige pas as die saad vir 'n nuwe pas, maar in plaas daarvan om die eerste element te ruil, ruil die tweede element met elke daaropvolgende element.Hierdie keer moet u ook nie die oorspronklike skikking by die uitvoer insluit nie.
Herhaal stap 2 tot klaar.
Hier is die kode voorbeeld:
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;
}
Ek is nie seker hoekom jy dit in die eerste plek sou wou doen nie.Die resulterende stel vir enige matig groot waardes van x en y sal groot wees, en sal eksponensieel groei soos x en/of y groter word.
Kom ons sê jou stel moontlike karakters is die 26 kleinletters van die alfabet, en jy vra jou aansoek om alle permutasies te genereer waar lengte = 5.As u aanvaar dat u nie genoeg geheue het nie, sal u 11 881 376 kry (d.w.s.26 tot die mag van 5) snare terug.Stamp daardie lengte tot 6, en jy sal 308 915 776 snare terugkry.Hierdie getalle word pynlik groot, baie vinnig.
Hier is 'n oplossing wat ek in Java saamgestel het.Jy sal twee runtime argumente moet verskaf (wat ooreenstem met x en y).Hê pret.
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);
}
}
}
}
Ek het dit vandag nodig gehad, en hoewel die antwoorde wat reeds gegee het my in die regte rigting gewys het, was dit nie heeltemal wat ek wou hê nie.
Hier is 'n implementering wat Heap se metode gebruik.Die lengte van die skikking moet ten minste 3 wees en vir praktiese oorwegings nie groter as 10 of so wees nie, afhangende van wat jy wil doen, geduld en klokspoed.
Inisialiseer voordat jy jou lus betree Perm(1 To N) met die eerste permutasie, Stack(3 To N) met nulle*, en Level met 2**.Aan die einde van die lus oproep NextPerm, wat vals sal terugkeer wanneer ons klaar is.
* VB sal dit vir jou doen.
** Jy kan NextPerm 'n bietjie verander om dit onnodig te maak, maar dit is duideliker soos hierdie.
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
Ander metodes word deur verskeie skrywers beskryf.Knuth beskryf twee, een gee leksikale orde, maar is kompleks en stadig, die ander staan bekend as die metode van gewone veranderinge.Jie Gao en Dianjun Wang het ook 'n interessante referaat geskryf.
In robyn:
str = "a"
100_000_000.times {puts str.next!}
Dit is redelik vinnig, maar dit gaan 'n rukkie neem =).Natuurlik kan jy by "aaaaaaaa" begin as die kort snare nie vir jou interessant is nie.
Ek het dalk die werklike vraag egter verkeerd geïnterpreteer - in een van die plasings het dit geklink asof jy net 'n bruteforce-biblioteek van snare nodig het, maar in die hoofvraag klink dit of jy 'n spesifieke string moet permuteer.
Jou probleem is ietwat soortgelyk aan hierdie een: http://beust.com/weblog/archives/000491.html (lys alle heelgetalle waarin nie een van die syfers hulself herhaal nie, wat gelei het tot 'n hele klomp tale wat dit opgelos het, met die ocaml ou wat permutasies gebruik, en 'n paar java ou wat nog 'n ander oplossing gebruik).
Hierdie kode in python, wanneer genoem met allowed_characters stel na [0,1] en maksimum 4 karakters, sal 2^4 resultate genereer:
['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()
Hoop dit is van nut vir jou.Werk met enige karakter, nie net syfers nie
Hier is 'n skakel wat beskryf hoe om permutasies van 'n string te druk.http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html
Alhoewel dit nie jou vraag presies beantwoord nie, is hier een manier om elke permutasie van die letters uit 'n aantal stringe van dieselfde lengte te genereer:bv. as jou woorde "koffie", "joomla" en "moodle" was, kan jy uitset verwag soos "coodle", "joodee", "joffle", ens.
Basies is die aantal kombinasies die (aantal woorde) tot die mag van (aantal letters per woord).Kies dus 'n ewekansige getal tussen 0 en die aantal kombinasies - 1, skakel daardie getal om na basis (aantal woorde), gebruik dan elke syfer van daardie getal as die aanwyser van watter woord om die volgende letter te neem.
bv:in die voorbeeld hierbo.3 woorde, 6 letters = 729 kombinasies.Kies 'n ewekansige getal:465.Skakel oor na basis 3:122020.Neem die eerste letter van woord 1, 2de van woord 2, 3de van woord 2, 4de van woord 0...en jy kry..."joffel".
As jy al die permutasies wou hê, lus net van 0 tot 728.Natuurlik, as jy net een ewekansige waarde kies, baie eenvoudiger minder verwarrende manier sou wees om oor die letters te lus.Met hierdie metode kan jy rekursie vermy as jy al die permutasies wil hê, en dit laat jou lyk asof jy Wiskunde ken(tm)!
As die aantal kombinasies buitensporig is, kan jy dit in 'n reeks kleiner woorde opbreek en hulle aan die einde saamvoeg.
c# iteratief:
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;
}
Daar is 'n iteratiewe Java-implementering in Ongewoon Wiskunde (werk vir 'n lys van voorwerpe):
/**
* 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
Hier is my siening van 'n nie-rekursiewe weergawe
Die pytoniese oplossing:
from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
