Vă mulțumim pentru susținere

Generați lista tuturor permutărilor posibile ale unui șir

Cum aș putea genera o listă a tuturor permutărilor posibile ale unui șir între lungimile caracterelor x și y, conținând o listă variabilă de caractere.

Orice limbă ar funcționa, dar ar trebui să fie portabilă.

0
adăugat editat
adăugat autor hippietrail

36 răspunsuri

@david: Both @Adam Backtrom and @Viper007Bond give some good advice so I thought I'd take their advice and see if I couldn't implement something, see below.

Ceea ce urmează iS un plugin numit WP Active Plugins Data </​​em> care analizează metadatele antetului pentru toate pluginurile active oricând este activat orice plugin și stochează toate metadatele fiecărui plugin într-un tablou în wp_options . Am proiectat-o ​​atât pentru pluginurile obișnuite WordPress, cât și pentru pluginurile multisite la nivel de site. Puteți să descărcați-o aici , dar și să copiați codul aici pentru recenzie:

9
adăugat
+1. Bună treabă, Mike. Mă întreb câte plug-uri vor ieși din acest StackExchange. :)
adăugat autor Annika Backstrom
Mulțumiri. De fapt, sper în multe, dar sper, de asemenea, că doar cei mai buni își vor intra în depozit. Există prea mult gunoi acolo chiar acum!
adăugat autor MikeSchinkel

Puteți să analizați meta datele pluginului (acele lucruri din partea de sus a fișierului), dar este mai bine pentru performanță dacă setați propria variabilă PHP cu un număr de versiune care se potrivește. Când actualizați pluginul, actualizați ambele numere de versiune.

Este ceva mai mult pentru tine pe termen scurt, dar mult mai bine pe termen lung.

2
adăugat
Ar putea fi mai bine ca performanța să definească doar o variabilă, dar nu este prea frumos să schimbi numărul versiunii la 2 locuri. Pentru teme, există o funcție similară wp_get_theme care este folosită și în exemple: codex.wordpress.org/Child_Themes Arată ca un design rău în WordPress, ar fi mai bine dacă am putea seta versiunea pluginului printr-o variabilă și apoi reutilizați variabila cu funcțiile wp_enqueue_style și wp_enqueue_script.
adăugat autor baptx

Există în ecranele de administrare: get_plugin_data () . În șabloane, cred că veți avea nevoie de pluginul pentru a ține acele date în PHP, de exemplu, setați o constantă sau globală sau ceva similar și păstrați această valoare sincronizată cu numărul versiunii antetului pluginului.

wp-settings.php calls wp_get_active_and_valid_plugins(), which pulls data from the active_plugins site option. This option only contains the path to the plugin file, and wp-settings.php only runs include_once on the file, so it's never parsed for the plugin metadata.

1
adăugat

Tocmai am bătut asta în Ruby:

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

S-ar putea să te uiți în limbajul API pentru funcțiile construite în permutarea tipului și ai putea să scrii un cod optimizat, dar dacă cifrele sunt atât de mari, nu sunt sigur că există o mulțime de rezultate pentru a avea multe rezultate .

Oricum, ideea din spatele codului începe cu șirul de lungime 0, apoi ține evidența tuturor șirurilor de lungime Z unde Z este dimensiunea curentă în iterație. Apoi treceți prin fiecare șir și adăugați fiecare caracter pe fiecare șir. În final, la sfârșit, eliminați oricare dintre ele care se află sub pragul x și returnați rezultatul.

Nu am testat-o ​​cu intrări potențial lipsite de semnificație (lista de caractere nulă, valori ciudate de x și y etc.).

0
adăugat
Acest cod este greșit. Aceasta va genera permutări invalide, cum ar fi cele cu caractere repetate. De exemplu, pentru șirul "abc", aceasta generează aceste permutări de mărimea 3: ["aaa", "aab", "aac", "aba", "abb", "abc", "aca" "bcb", "bbc", "bcc", "bcc", "bcc", "bac", "bac" "," cba "," cbb "," cbc "," cca "," ccb "," ccc "]. Acest lucru este incorect.
adăugat autor pmc255

Veți obține o mulțime de corzi, asta e sigur ...

\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
Where, x and y is how you define them and r is the number of characters we are selecting from --if I am understanding you correctly. You should definitely generate these as needed and not get sloppy and say, generate a powerset and then filter the length of strings.

Următoarele nu sunt cu siguranță cel mai bun mod de a genera aceste lucruri, dar este un lucru interesant, cel mai puțin.

Knuth (volumul 4, fascicula 2, 7.2.1.3) ne spune că (s, t) -combinarea este echivalentă cu s + 1 lucruri luate la un moment dat cu repetiție - o combinație (s, t) Knuth care este egal cu {t \ alege {s + t } http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20%7Bs+t%7D%7D . Putem imagina acest lucru prin generarea mai întâi a fiecărei (s, t) -combinări în formă binară (deci, a lungimii (s + t)) și numărarea numărului de 0 la stânga fiecărui 1.

10001000011101 --> becomes the permutation: {0, 3, 4, 4, 4, 1}

0
adăugat

Deși acest lucru nu răspunde exact la întrebarea dvs., iată o modalitate de a genera fiecare permutare a literelor dintr-un număr de șiruri de aceeași lungime: de exemplu, în cazul în care cuvintele dvs. erau "cafea", "joomla" și "moodle" așteaptă ieșiri ca "cochetă", "joodee", "joffle" etc.

Practic, numărul de combinații este (numărul de cuvinte) la puterea (numărul de litere pe cuvânt). Deci, alegeți un număr aleatoriu între 0 și numărul de combinații - 1, convertiți numărul în bază (numărul de cuvinte), apoi folosiți fiecare cifră a acelui număr ca indicator pentru care cuvânt să luați următoarea literă din.

de exemplu: în exemplul de mai sus. 3 cuvinte, 6 litere = 729 de combinații. Alegeți un număr aleatoriu: 465. Conversia la baza 3: 122020. Luați prima literă din cuvântul 1, al doilea de la cuvântul 2, al treilea de la cuvântul 2, al patrulea de la cuvântul 0 ... și obțineți ... "joofle".

Dacă v-ați dorit toate permutările, pur și simplu între 0 și 728. Bineînțeles, dacă alegeți doar o valoare aleatorie, o modalitate mai puțin confuză simpler ar fi să vă bucurați de litere. Această metodă vă permite să evitați recursul, dacă doriți toate permutările, plus vă face să arătați că știți că matematica (tm) !

Dacă numărul de combinații este excesiv, îl puteți descompune într-o serie de cuvinte mai mici și le puteți concatena la sfârșit.

0
adăugat

Here is a link that describes how to print permutations of a string. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

0
adăugat

Unele coduri de lucru bazate pe răspunsul lui Sarp :

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);
    }
}
0
adăugat
Ca comentariu, rețineți că pentru un șir cu caractere repetate acest lucru nu va produce permutările unice. Acest lucru ar putea fi rezolvat cu un hash, dar aceasta ar putea fi o problemă cu șiruri lungi.
adăugat autor Glenn
S-ar putea să doriți să utilizați caracterele char în loc de șiruri de caractere pentru a face acest lucru să ruleze mai repede, deoarece șirurile sunt imuabile în java.
adăugat autor Abhijeet Kashnia
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
0
adăugat

În Perl, dacă doriți să vă restrângeți la alfabetul cu litere mici, puteți face acest lucru:

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

Aceasta oferă toate șirurile posibile între 1 și 4 caractere folosind caractere minuscule. Pentru majuscule, schimbați "a" la "A" și "zzzz" la "ZZZZ" .

Pentru caz mixt, devine mult mai greu și, probabil, imposibil de realizat cu unul dintre operatorii incluși de Perl.

0
adăugat

Răspunsul Ruby care funcționează:

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")
0
adăugat
Pentru o linie liniară în Ruby: stackoverflow.com/questions/5773961/…
adăugat autor dojosto

Iată o versiune nerecursivă la care am venit, în javascript. Nu se bazează pe una nerecursivă a lui Knuth de mai sus, deși are unele asemănări în schimbarea elementelor. Am verificat corectitudinea pentru matrice de intrări de până la 8 elemente.

O optimizare rapidă ar fi efectuarea înainte de zbor a matricei out și evitarea push () .

Ideea de bază este:

  1. Dat fiind o singură matrice sursă, generați un prim set nou de seturi care schimbă primul element cu fiecare element ulterior, la rândul său, de fiecare dată când alte elemente rămân neperturbate. de ex .: dat 1234, generați 1234, 2134, 3214, 4231.

  2. Folosiți fiecare matrice din pasul anterior ca semințe pentru o nouă trecere, dar în loc de a schimba primul element, swap al doilea element cu fiecare element ulterior. De asemenea, de această dată, nu includeți matricea originală în ieșire.

  3. Repetați pasul 2 până când ați terminat.

Iată exemplul de cod:

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;
}
0
adăugat

Există o implementare Java iterativă în UncommonsMaths (funcționează pentru o listă de obiecte ):

/**
 * 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 nextPermutationAsList(List destination)
{
    generateNextPermutationIndices();
    // Generate actual permutation.
    destination.clear();
    for (int i : permutationIndices)
    {
        destination.add(elements[i]);
    }
    return destination;
}

sursă completă

0
adăugat

S-ar putea să vă uitați la " Enumerarea eficientă a subseturilor unui set ", care descrie un algoritm pentru a face o parte din ceea ce doriți - generați rapid toate subseturile de caractere N de la lungimea x la y. Acesta conține o implementare în C.

Pentru fiecare subset, ar trebui să generați toate permutările. De exemplu, dacă doriți 3 caractere din "abcde", acest algoritm vă va oferi "abc", "abd", "abe" ... dar va trebui să le permutați pe fiecare pentru a obține "acb", "bac", "bca" etc.

0
adăugat

Sunt multe răspunsuri bune aici. De asemenea, sugerez o soluție foarte simplă recursivă în C ++.

#include 
#include 

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

Note: strings with repeated characters will not produce unique permutations.

0
adăugat
Această soluție este excelentă și merită o atenție sporită.
adăugat autor Mike S
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

Iată care este versiunea mea non-recursivă

0
adăugat

Soluție nerecursivă în conformitate cu exemplul Knuth, Python:

def nextPermutation(perm):
    k0 = None
    for i in range(len(perm)-1):
        if perm[i]< 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)
0
adăugat
Ce este interesant este faptul că nextPermutation () este apatrid? este nevoie doar de intrare pentru a permutate și indici nu sunt întreținute de la iterație la iterație. Este capabil să facă acest lucru presupunând că intrările inițiale au fost sortate și căutarea indiciilor ( k0 și l0 ), în funcție de locul în care ordinea este menținută. Sortarea unei intrări ca "54321" -> "12345" ar permite acestui algoritm să găsească toate permutările așteptate. Dar, din moment ce face o bună muncă suplimentară pentru a re-găsi acei indici pentru fiecare per
adăugat autor spaaarky21
De fapt, aceasta nu funcționează și nu / când șirul nu este sortat. Dacă încercați cu "54321" este afișat (singur) șirul ONE .
adăugat autor tonjo

Soluția pythonic:

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

... și aici este versiunea 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;
}
0
adăugat

Există mai multe moduri de a face acest lucru. Metodele obișnuite utilizează recursul, memoizarea sau programarea dinamică. Ideea de bază este că produceți o listă cu toate șirurile de lungime 1, apoi în fiecare iterație, pentru toate șirurile produse în ultima iterație, adăugați acel șir concatenat cu fiecare caracter din șir individual. (indicele variabile din codul de mai jos ține evidența începutului ultimei și următoarei iterații)

Unele pseudocode:

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

atunci ar trebui să eliminați toate șirurile mai mici de x în lungime, acestea vor fi primele (x-1) * len (originalString) intrări din listă.

0
adăugat
De ce să stocați prima listă de elemente și apoi să le ștergeți? (cu referire la linia 1 și 3 din pseudocod).
adăugat autor Håvard Geithus
Ce este y (linia 4)?
adăugat autor Jaseem
@Jaseem Din întrebarea: "toate permutările posibile ale unui șir între caracterele x și y în lungime"
adăugat autor cksubs

Nu sunt sigur de ce ai vrea să faci asta în primul rând. Setul rezultat pentru orice valori moderat mari ale lui x și y va fi enorm și va crește exponențial, pe măsură ce x și / sau y devin mai mari.

Să presupunem că setul de caractere posibile este 26 de litere mici ale alfabetului și cereți aplicației dvs. să genereze toate permutările în cazul în care lungimea = 5. Dacă presupuneți că nu veți rămâne fără memorie, veți primi 11.881.376 (adică 26 la putere din 5) șiruri de caractere înapoi. Loviți-o cu o lungime de până la 6, și vei primi 308.915.776 șiruri de caractere înapoi. Aceste cifre sunt dureros de mari, foarte repede.

Iată o soluție pe care am pus-o împreună în Java. Va trebui să furnizați două argumente de rulare (corespunzătoare lui x și y). A se distra.

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);
            }
        }
    }
}
0
adăugat
De mult timp, dar nu le generați cu repetiție?
adăugat autor Kakira

Soluție recursivă în 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
0
adăugat
@Sper Centel: funcționează acest cod în C ++? << code> string </ code >>
adăugat autor Lazer

Iată un cuvânt simplu C # soluție recursivă:

Metodă:

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

Tonuri:

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

Aici este o soluție simplă în C #.

El generează numai permutările distincte ale unui șir dat.

    static public IEnumerable 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;
        }
    }
0
adăugat
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 concat(String c, Set lst) {
        HashSet ret_set = new HashSet();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet all_perm(String a) {
        HashSet set = new HashSet();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i
0
adăugat
Versiune non-recursivă: stackoverflow.com/a/28527943/1266326
adăugat autor MLProgrammer-CiM

permute (ABC) -> A.perm(BC) -> A.perm[B.perm(C)] -> A.perm[(*BC), (CB*)] -> [(*ABC), (BAC), (BCA*), (*ACB), (CAB), (CBA*)] To remove duplicates when inserting each alphabet check to see if previous string ends with the same alphabet (why? -exercise)

public static void main(String[] args) {

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

static Vector permStr(String str){

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

    char start = str.charAt(0);
    Vector endStrs = permStr(str.substring(1));
    Vector newEndStrs = new Vector();
    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;
}

Tipărește toate permutările fără duplicate

0
adăugat

Acest cod în Python, când este apelat cu allowed_characters setat la [0,1] și maxim 4 caractere, generează 2 ^ 4 rezultate:

<10000>, «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()

Sper că acest lucru vă este de folos. Lucrează cu orice personaj, nu numai cu numere

0
adăugat
Aceasta nu este o selecție de permutări, ci o subsetare, adică ABC & 001 = C, în timp ce o permutare validă trebuie să aibă toate cele trei caractere.
adăugat autor Schultz9999
uh? Îmi pare rău că nu înțeleg ce spui. Dacă o rezolvi lăsa o versiune fixă, voi comunica wiki chestia
adăugat autor droope

Aveam nevoie de asta astăzi și, deși răspunsurile deja date mi-au indicat în direcția cea bună, nu erau chiar ceea ce vroiam.

Iată o implementare folosind metoda lui Heap. Lungimea matricei trebuie să fie de cel puțin 3 și pentru considerente practice să nu fie mai mare de 10 sau cam asa ceva, în funcție de ceea ce vrei să faci, răbdarea și viteza de ceas.

Înainte de a introduce buclele, inițializați Perm (1 To N) cu prima permutare, Stack (3 To N) cu zeroes * și Level cu 2 **. La sfârșitul apelului de buclă NextPerm , care va reveni la fals când am terminat.

* VB va face asta pentru tine.

** Poți schimba puțin NextPerm pentru a face acest lucru inutil, dar este mai clar așa.

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

Alte metode sunt descrise de diverși autori. Knuth descrie două, una le dă ordine lexicală, dar este complexă și lentă, cealaltă este cunoscută ca metoda schimbărilor simple. Jie Gao și Dianjun Wang au scris și o lucrare interesantă.

0
adăugat

Este mai bine să folosiți backtracking

#include 
#include 

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;
}
0
adăugat
Cea mai bună soluție everrrrrrrrr
adăugat autor GrowinMan
Este o metodă foarte ușor de citit și ușor de înțeles.
adăugat autor joey rohan

c iterativ:

public List Permutations(char[] chars)
    {
        List words = new List();
        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;
    }
0
adăugat

Următoarea recursiune Java imprimă toate permutările unui șir dat:

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

Următoare este versiunea actualizată a metodei de mai sus "permut" care face n! (n factorial) mai puțin recursive față de metoda de mai sus

//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()));
   }
}
0
adăugat
@TaoZhang mulțumiri pentru completare, nu l-am copiat de oriunde este posibil ca cineva a creat algo similare. Oricum, am actualizat codul de mai sus pentru apeluri mai puțin recursive
adăugat autor Ramy
Aceasta este soluția cea mai curată și cred că am văzut-o înainte în cartea "Cracking the Coding Interview"
adăugat autor Tao Zhang

O soluție recursivă în Python. Lucrul bun în legătură cu acest cod este că exportă un dicționar, cu chei ca șiruri de caractere și toate permutările posibile ca valori. Toate lungimile posibile ale șirului sunt incluse, deci, de fapt, creați un superset.

Dacă aveți nevoie doar de permutările finale, puteți șterge alte chei din dicționar.

În acest cod, dicționarul permutărilor este global.

În cazul de bază, stochez valoarea ca ambele posibilități într-o listă. perms ['ab'] = ['ab', 'ba'] .

Pentru lungimi de șir mai mari, funcția se referă la lungimile mai mici ale șirului și încorporează permutările calculate anterior.

Funcția are două lucruri:

  • se solicită cu un șir mai mic
  • returnează o listă de permutări ale unui șir special dacă este deja disponibilă. Dacă s-au returnat la sine, acestea vor fi folosite pentru a atașa caracterul și pentru a crea permutări mai noi.

Scump pentru memorie.

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]
0
adăugat

Soluție recursivă cu metoda main () a driverului.

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

    for(int i=0; i

}

0
adăugat

Ei bine, aici este o soluție O (n!) Elegantă, nerecursivă:

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;
    }
0
adăugat

cod scrise pentru java:

pachet namo.algorithms;

import java.util.Scanner;

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

}

0
adăugat

Posibilele permutări de șir pot fi calculate utilizând funcția recursivă. Mai jos este una dintre soluțiile posibile.

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 getPerm(String s, int index) {
        ArrayList perm = new ArrayList();

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

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

        for(String pp : p) {
            for (int idx=0; idx perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}
0
adăugat