κατάλογος όλων των δυνατών μεταθέσεων μιας σειράς Δημιουργία

ψήφοι
143

Πώς θα πάω για τη δημιουργία μια λίστα με όλες τις πιθανές παραλλαγές μιας σειράς μεταξύ x και y χαρακτήρες, που περιέχει μια μεταβλητή λίστα των χαρακτήρων.

Κάθε γλώσσα θα μπορούσε να λειτουργήσει, αλλά θα πρέπει να είναι φορητό.

Δημοσιεύθηκε 02/08/2008 στις 07:57
πηγή χρήστη
Σε άλλες γλώσσες...                            


35 απαντήσεις

ψήφοι
67

Υπάρχουν διάφοροι τρόποι για να γίνει αυτό. Κοινές μέθοδοι χρησιμοποιούν αναδρομή, memoization, ή δυναμικός προγραμματισμός. Η βασική ιδέα είναι ότι μπορείτε να παράγει μια λίστα με όλες τις χορδές του μήκους 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-1) * len (originalString) καταχωρήσεις στη λίστα.

Απαντήθηκε 02/08/2008 στις 08:48
πηγή χρήστη

ψήφοι
35

Είναι καλύτερο να χρησιμοποιήσετε οπισθοδρόμηση

#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;
}
Απαντήθηκε 10/01/2012 στις 19:00
πηγή χρήστη

ψήφοι
24

Θα έχετε την ευκαιρία να πάρετε μια πολύ χορδές, αυτό είναι σίγουρο ...

\ sum_ {i = x} ^ y {\ frac {r!} {{(ri)}!}} http://www.codecogs.com/eq.latex?%5Csum_%7Bi=x%7D%5Ey% 20% 7Β% 20% 5Cfrac% 7BR% 7D% 7Β% 7Β (ri)% 7D% 7D% 20% 7D!
Όπου, χ και Υ είναι το πώς μπορείτε να ορίσετε και r είναι ο αριθμός των χαρακτήρων που επιλέγετε από - -αν είμαι εσείς που καταλαβαίνετε σωστά. Θα πρέπει σίγουρα να δημιουργήσει αυτές ανάλογα με τις ανάγκες και να μην πάρει προχειρότητα και να πω, δημιουργούν ένα Powerset και, στη συνέχεια, φιλτράρετε το μήκος των χορδών.

Το παρακάτω σίγουρα δεν είναι ο καλύτερος τρόπος για να δημιουργήσει αυτά, αλλά είναι μια ενδιαφέρουσα άκρη, κανένας-το-λιγότερο.

Knuth (όγκος 4, δεμάτιο 2, 7.2.1.3) μας λέει ότι (s, t) -σύνολα συζευγμένων είναι ισοδύναμο με s + 1 πράγματα ληφθεί t σε έναν χρόνο με την επανάληψη - ένα (s, t) -σύνολα συζευγμένων είναι σημειογραφία χρησιμοποιείται από Knuth που είναι ίση με {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}

Απαντήθηκε 05/08/2008 στις 05:57
πηγή χρήστη

ψήφοι
14

Μη αναδρομική λύση σύμφωνα με Knuth, Python παράδειγμα:

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)
Απαντήθηκε 09/11/2010 στις 14:58
πηγή χρήστη

ψήφοι
12

Υπάρχουν πολλές καλές απαντήσεις εδώ. Προτείνω επίσης μια πολύ απλή επαναλαμβανόμενη λύση σε 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;
    });
}

Σημείωση : χορδές με επαναλαμβανόμενες χαρακτήρες δεν θα παράγει μοναδικές παραλλαγές.

Απαντήθηκε 08/01/2014 στις 12:00
πηγή χρήστη

ψήφοι
12

Εδώ είναι μια απλή λύση σε 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;
        }
    }
Απαντήθηκε 05/07/2010 στις 10:06
πηγή χρήστη

ψήφοι
12

Μερικά κώδικα εργασίας που βασίζεται σε Java σε απάντηση 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);
    }
}
Απαντήθηκε 04/04/2010 στις 19:18
πηγή χρήστη

ψήφοι
12

Μπορείτε να δείτε στις ομάδες « Αποδοτικές Απαριθμώντας τα υποσύνολα ενός συνόλου », η οποία περιγράφει έναν αλγόριθμο για να κάνει από την πλευρά της ό, τι θέλετε - γρήγορα να δημιουργήσει όλα τα υποσύνολα του N χαρακτήρες από το μήκος x έως y. Περιέχει μια εφαρμογή σε C.

Για κάθε υποσύνολο, θα πρέπει ακόμα να δημιουργήσει όλες τις παραλλαγές. Για παράδειγμα, αν ήθελε 3 χαρακτήρες από το «ABCDE», ο αλγόριθμος αυτός θα σας δώσει «abc», «Abe» «abd» ... αλλά θα πρέπει να μεταθέτει ο καθένας να πάρει «ACB», «bac», "BCA", κ.λπ.

Απαντήθηκε 14/11/2008 στις 20:36
πηγή χρήστη

ψήφοι
8

Απλά χτυπημένη αυτό επάνω γρήγορα σε 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

Μπορείτε να δείτε σε γλώσσα API για ενσωματωμένες λειτουργίες τύπου μετάθεση, και να είστε σε θέση να γράψω περισσότερα βελτιστοποιημένο κώδικα, αλλά αν οι αριθμοί είναι όλα τόσο ψηλά, δεν είμαι σίγουρος ότι υπάρχει ένα μεγάλο μέρος μιας ανάποδο έχει πολλά αποτελέσματα .

Anyways, η ιδέα πίσω από τον κώδικα είναι να ξεκινήσει με κορδόνι μήκους 0, στη συνέχεια, να παρακολουθείτε όλες τις χορδές του μήκους Ζ, όπου Ζ είναι το τρέχον μέγεθος της επανάληψης. Στη συνέχεια, περνούν από κάθε σειρά και επισυνάπτει κάθε χαρακτήρα σε κάθε χορδή. Τέλος, στο τέλος, αφαιρέστε κάθε που ήταν κάτω από το όριο x και επιστρέφει το αποτέλεσμα.

Εγώ δεν το δοκιμάσετε με δυνητικά νόημα εισόδου (κατάλογος null χαρακτήρα, παράξενα τιμές των x και y, κλπ).

Απαντήθηκε 02/08/2008 στις 08:56
πηγή χρήστη

ψήφοι
7

Ruby απάντηση που λειτουργεί:

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")
Απαντήθηκε 20/04/2012 στις 01:21
πηγή χρήστη

ψήφοι
7

μετατίθενται (ABC) -> A.perm (BC) -> A.perm [B.perm (C)] -> A.perm [( * Β Γ), (Γ Β * )] -> [( * Α π.Χ. ), (Β Α Γ), (BC Α * ), ( * Α CB), (Γ Α Β), (CB A * )] για να αφαιρέσετε διπλότυπα όταν εισάγοντας κάθε επιταγή αλφαβήτου για να δούμε εάν η προηγούμενη στοιχειοσειρά τελειώνει με τον ίδιο αλφάβητο (γιατί; -exercise)

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

Εκτυπώνει όλες οι μεταθέσεις χωρίς διπλότυπα

Απαντήθηκε 22/02/2011 στις 19:45
πηγή χρήστη

ψήφοι
7

... και εδώ είναι η έκδοση 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;
}
Απαντήθηκε 07/02/2011 στις 22:56
πηγή χρήστη

ψήφοι
7

Στην Perl, αν θέλετε να περιορίσετε τον εαυτό σας στην πεζά αλφάβητο, μπορείτε να το κάνετε αυτό:

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

Αυτό δίνει όλες τις πιθανές σειρές μεταξύ 1 και 4 χαρακτήρες χρησιμοποιώντας πεζούς χαρακτήρες. Για κεφαλαία, αλλάξτε "a"σε "A"και "zzzz"σε "ZZZZ".

Για μικτή περίπτωση γίνεται πολύ πιο δύσκολο, και ίσως να μην εφικτό με μία από τις ενσωματωμένες φορείς της Perl έτσι.

Απαντήθηκε 15/02/2009 στις 11:02
πηγή χρήστη

ψήφοι
7

Εδώ είναι μια απλή λέξη, 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);
Απαντήθηκε 20/10/2008 στις 01:17
πηγή χρήστη

ψήφοι
7

Αναδρομικές διάλυμα σε 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;
            }
        }
}
Απαντήθηκε 29/09/2008 στις 02:34
πηγή χρήστη

ψήφοι
7

Αυτή είναι μια μετάφραση της έκδοσης Ruby Mike, σε 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)))))
Απαντήθηκε 16/09/2008 στις 06:15
πηγή χρήστη

ψήφοι
6

Οι παρακάτω αναδρομή εκτυπώσεις Java όλες οι παραλλαγές μιας συγκεκριμένης συμβολοσειράς:

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

Μετά είναι η ενημερωμένη έκδοση του παραπάνω μέθοδο «PERMUT» που κάνει n! (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()));
   }
}
Απαντήθηκε 19/06/2013 στις 05:23
πηγή χρήστη

ψήφοι
5

Εδώ είναι μια μη αναδρομική εκδοχή ήρθα με, σε javascript. Δεν βασίζεται σε μη αναδρομικό ένα Knuth του παραπάνω, αν και έχει κάποιες ομοιότητες με την εναλλαγή των στοιχείων. Έχω επαληθεύσει την ορθότητα των πληροφοριών για συστοιχίες εισόδου έως 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;
}
Απαντήθηκε 03/08/2011 στις 08:11
πηγή χρήστη

ψήφοι
5
import java.util.*;

public class all_subsets {
    public static void main(String[] args) {
        String a = "abcd";
        for(String s: all_perm(a)) {
            System.out.println(s);
        }
    }

    public static Set<String> concat(String c, Set<String> lst) {
        HashSet<String> ret_set = new HashSet<String>();
        for(String s: lst) {
            ret_set.add(c+s);
        }
        return ret_set;
    }

    public static HashSet<String> all_perm(String a) {
        HashSet<String> set = new HashSet<String>();
        if(a.length() == 1) {
            set.add(a);
        } else {
            for(int i=0; i<a.length(); i++) {
                set.addAll(concat(a.charAt(i)+"", all_perm(a.substring(0, i)+a.substring(i+1, a.length()))));
            }
        }
        return set;
    }
}
Απαντήθηκε 24/10/2010 στις 23:01
πηγή χρήστη

ψήφοι
4

Δεν είμαι σίγουρος γιατί θα θέλετε να το κάνετε αυτό στην πρώτη θέση. Το σύνολο που προκύπτει για κάθε μετρίως μεγάλες τιμές του x και y θα είναι τεράστια και θα αυξηθεί εκθετικά όσο x ή / και y μεγαλώνουν.

Ας πούμε ότι σας σύνολο των πιθανών χαρακτήρες είναι τα 26 κεφαλαία γράμματα του αλφαβήτου, και να σας ρωτήσω την αίτησή σας για να δημιουργήσει όλες τις παραλλαγές όπου το μήκος = 5. Αν υποθέσουμε ότι δεν τρέχει έξω από τη μνήμη θα έχετε 11.881.376 (ήτοι 26 στην εξουσία 5) σειρές πίσω. Χτύπημα αυτό το μήκος έως 6, και θα πάρετε 308.915.776 χορδές πίσω. Αυτοί οι αριθμοί πάρει οδυνηρά μεγάλο, πολύ γρήγορα.

Εδώ είναι μια λύση έβαλα μαζί σε Java. Θα πρέπει να παρέχει δύο επιχειρήματα χρόνου εκτέλεσης (που αντιστοιχεί στο 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);
            }
        }
    }
}
Απαντήθηκε 02/08/2008 στις 10:40
πηγή χρήστη

ψήφοι
3

Χρειαζόμουν αυτό σήμερα, και παρόλο που οι απαντήσεις που έχουν ήδη δοθεί μου επισήμανε προς τη σωστή κατεύθυνση, δεν ήταν ακριβώς αυτό που ήθελα.

Εδώ είναι μια εφαρμογή με τη μέθοδο σωρού του. Το μήκος της συστοιχίας πρέπει να είναι τουλάχιστον 3 και για πρακτικούς λόγους δεν είναι μεγαλύτερο από 10 ή έτσι, ανάλογα με το τι θέλετε να κάνετε, την υπομονή και την ταχύτητα του ρολογιού.

Πριν μπείτε βρόχο σας, εκκινούν Perm(1 To N)με την πρώτη μετάθεση, Stack(3 To N)με μηδενικά *, και Levelμε 2**. Στο τέλος της κλήσης βρόχου NextPerm, που θα επιστρέψει 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

Άλλες μέθοδοι περιγράφονται από διάφορους συγγραφείς. Knuth περιγράφει δύο, το ένα δίνει λεξιλογικό παραγγελία, αλλά είναι πολύπλοκη και αργή, η άλλη είναι γνωστή ως η μέθοδος της πεδιάδας αλλαγές. Jie Gao και Dianjun Wang έγραψε επίσης μια ενδιαφέρουσα χαρτί.

Απαντήθηκε 02/10/2011 στις 10:13
πηγή χρήστη

ψήφοι
2

Εδώ είναι μια σύνδεση που περιγράφει τον τρόπο εκτύπωσης παραλλαγές μιας συμβολοσειράς. http://nipun-linuxtips.blogspot.in/2012/11/print-all-permutations-of-characters-in.html

Απαντήθηκε 13/02/2014 στις 22:08
πηγή χρήστη

ψήφοι
2

Αυτός ο κώδικας σε Python, όταν καλείται με την 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()

Η ελπίδα αυτή είναι χρήσιμη για εσάς. Λειτουργεί με οποιοδήποτε χαρακτήρα, όχι μόνο τους αριθμούς

Απαντήθηκε 26/05/2011 στις 15:22
πηγή χρήστη

ψήφοι
2

Σε ρουμπίνι:

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

Είναι αρκετά γρήγορο, αλλά πρόκειται να πάρει κάποιο χρόνο =). Φυσικά, μπορείτε να ξεκινήσετε σε «aaaaaaaa» αν οι σύντομες σειρές δεν είναι ενδιαφέρουσες για εσάς.

Θα ήθελα να έχουν παρερμηνεύσει το πραγματικό ερώτημα αν και - σε μία από τις θέσεις που ακουγόταν σαν απλά χρειάζεται μια βιβλιοθήκη bruteforce της χορδές, αλλά το κύριο ερώτημα που ακούγεται σαν να πρέπει να permutate μια συγκεκριμένη σειρά.

Το πρόβλημά σας είναι κάπως παρόμοιο με αυτό: http://beust.com/weblog/archives/000491.html (κατάλογος όλα ακέραιοι με την οποία κανένα από τα ψηφία επαναλαμβάνονται, η οποία οδήγησε σε ένα σωρό γλώσσες που επίλυσης, με το OCaml άντρας που χρησιμοποιούν παραλλαγές, και κάποιος τύπος java χρησιμοποιώντας μια ακόμη λύση).

Απαντήθηκε 15/09/2008 στις 18:32
πηγή χρήστη

ψήφοι
0

Οι πιθανοί συνδυασμοί συμβολοσειρά μπορεί να υπολογιστεί χρησιμοποιώντας αναδρομική συνάρτηση. Παρακάτω είναι μία από τις πιθανές λύσεις.

public static String insertCharAt(String s, int index, char c) {
        StringBuffer sb = new StringBuffer(s);
        StringBuffer sbb = sb.insert(index, c);
        return sbb.toString();
}

public static ArrayList<String> getPerm(String s, int index) {
        ArrayList<String> perm = new ArrayList<String>();

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

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

        for(String pp : p) {
            for (int idx=0; idx<pp.length()+1; idx++) {
                String ss = insertCharAt(pp, idx, c);
                perm.add(ss);
            }
        }

        return perm;    
}

public static void testGetPerm(String s) {
        ArrayList<String> perm = getPerm(s,0);
        System.out.println(s+" --> total permutation are :: "+perm.size());
        System.out.println(perm.toString());
}
Απαντήθηκε 06/02/2017 στις 06:00
πηγή χρήστη

ψήφοι
0

κώδικα που γράφεται για τη γλώσσα Java:

namo.algorithms πακέτο?

εισαγωγής java.util.Scanner?

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

}

Απαντήθηκε 05/06/2016 στις 08:42
πηγή χρήστη

ψήφοι
0

Καλά εδώ είναι ένα κομψό, μη-αναδρομικές, O (n!) Λύση:

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;
    }
Απαντήθηκε 27/06/2015 στις 08:44
πηγή χρήστη

ψήφοι
0

Το pythonic διάλυμα:

from itertools import permutations
s = 'ABCDEF'
p = [''.join(x) for x in permutations(s)]
Απαντήθηκε 13/07/2014 στις 08:51
πηγή χρήστη

ψήφοι
0
def permutation(str)
  posibilities = []
  str.split('').each do |char|
    if posibilities.size == 0
      posibilities[0] = char.downcase
      posibilities[1] = char.upcase
    else
      posibilities_count = posibilities.length
      posibilities = posibilities + posibilities
      posibilities_count.times do |i|
        posibilities[i] += char.downcase
        posibilities[i+posibilities_count] += char.upcase
      end
    end
  end
  posibilities
end

Εδώ είναι η δική μου σε μια μη αναδρομική εκδοχή

Απαντήθηκε 23/01/2014 στις 04:28
πηγή χρήστη

ψήφοι
0

Αναδρομική λύση με οδηγό main()τη μέθοδο.

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

    for(int i=0; i<remaining.length(); i++) {
        String newRemaining = remaining.replaceFirst(remaining.charAt(i)+"", "");
        stringPermutations(newstring+remaining.charAt(i), newRemaining);
    }
}

public static void main(String[] args) {
    String string = "abc";
    AllPermutationsOfString.stringPermutations("", string); 
}

}

Απαντήθηκε 19/10/2013 στις 02:34
πηγή χρήστη

ψήφοι
0
def gen( x,y,list): #to generate all strings inserting y at different positions
list = []
list.append( y+x )
for i in range( len(x) ):
    list.append( func(x,0,i) + y + func(x,i+1,len(x)-1) )
return list 

def func( x,i,j ): #returns x[i..j]
z = '' 
for i in range(i,j+1):
    z = z+x[i]
return z 

def perm( x , length , list ): #perm function
if length == 1 : # base case
    list.append( x[len(x)-1] )
    return list 
else:
    lists = perm( x , length-1 ,list )
    lists_temp = lists #temporarily storing the list 
    lists = []
    for i in range( len(lists_temp) ) :
        list_temp = gen(lists_temp[i],x[length-2],lists)
        lists += list_temp 
    return lists
Απαντήθηκε 22/08/2013 στις 18:51
πηγή χρήστη

ψήφοι
0

Ένα αναδρομικό διάλυμα σε Python. Το καλό πράγμα για αυτόν τον κώδικα είναι ότι εξάγει ένα λεξικό, με πλήκτρα και χορδές και όλες τις πιθανές παραλλαγές ως τιμές. Όλα τα πιθανά μήκη χορδών περιλαμβάνονται, τόσο στην ουσία, δημιουργείτε ένα υπερσύνολο.

Εάν χρειάζεστε μόνο τις τελικές παραλλαγές, μπορείτε να διαγράψετε άλλα πλήκτρα από το λεξικό.

Σε αυτόν τον κώδικα, το λεξικό των μεταθέσεων είναι παγκόσμια.

Στο βασικό σενάριο, που αποθηκεύει την τιμή καθώς και οι δύο δυνατότητες σε μια λίστα. perms['ab'] = ['ab','ba'].

Για υψηλότερες μήκη συμβολοσειρά, η συνάρτηση αναφέρεται σε κατώτερο μήκη χορδών και ενσωματώνει τις προηγουμένως υπολογισθείσα μεταθέσεις.

Η λειτουργία κάνει δύο πράγματα:

  • αυτοαποκαλείται με ένα μικρότερο κορδόνι
  • επιστρέφει μια λίστα των μεταθέσεων μιας συγκεκριμένης συμβολοσειράς αν είναι ήδη διαθέσιμα. Αν επέστρεψε στον εαυτό του, αυτά θα χρησιμοποιηθούν για να προσθέσετε το χαρακτήρα και τη δημιουργία νεότερες παραλλαγές.

Ακριβά για τη μνήμη.

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]
Απαντήθηκε 05/07/2013 στις 05:15
πηγή χρήστη

ψήφοι
0

Υπάρχει μια επαναληπτική εφαρμογή Java σε 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;
}

Πλήρης πηγή

Απαντήθηκε 07/05/2013 στις 02:18
πηγή χρήστη

ψήφοι
0

γ # επαναληπτική:

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;
    }
Απαντήθηκε 26/07/2012 στις 16:20
πηγή χρήστη

ψήφοι
0

Αν και αυτό δεν απαντά στην ερώτησή σας ακριβώς, εδώ είναι ένας τρόπος για να δημιουργήσει κάθε μετάθεση των γραμμάτων από τον αριθμό των χορδών του ίδιου μήκους: π.χ., αν τα λόγια σας ήταν «καφέ», «joomla» και «moodle», μπορείτε να αναμένουμε εξόδου, όπως "coodle", "joodee", "joffle", κ.λπ.

Βασικά, ο αριθμός των συνδυασμών είναι ο (αριθμός λέξεων) με τη δύναμη του (αριθμός των γραμμάτων κάθε λέξης). Έτσι, επιλέγουν έναν τυχαίο αριθμό μεταξύ 0 και τον αριθμό των συνδυασμών - 1, μετατρέψετε αυτόν τον αριθμό στη βάση (αριθμός λέξεων), στη συνέχεια, χρησιμοποιήστε κάθε ψηφίο του αριθμού ως ένδειξη για την οποία λέξη για να κάνει το επόμενο γράμμα από.

π.χ.: στο παραπάνω παράδειγμα. 3 λέξεις, 6 γράμματα = 729 συνδυασμούς. Επιλέξτε έναν τυχαίο αριθμό: 465. Μετατροπή σε βασίσει 3: 122020. Πάρτε το πρώτο γράμμα από την λέξη 1, 2 από την λέξη 2, 3 από την λέξη 2, 4 από στόμα σε 0 ... και θα πάρει ... «joofle».

Αν ήθελε όλες τις παραλλαγές, μόλις βρόχο από το 0 έως το 728. Φυσικά, αν είστε απλά επιλέγοντας μία τυχαία τιμή, μια πολύ απλούστερη λιγότερο σύγχυση τρόπος θα ήταν να βρόχο πάνω από τα γράμματα. Η μέθοδος αυτή επιτρέπει να αποφευχθεί η αναδρομή, θα πρέπει να θέλετε όλες τις παραλλαγές, καθώς θα σας κάνει να μοιάζουν με ξέρετε Μαθηματικά (tm) !

Εάν ο αριθμός των συνδυασμών είναι υπερβολική, μπορείτε να το σπάσει σε μια σειρά από μικρότερες λέξεις και ενώσετε τους στο τέλος.

Απαντήθηκε 16/09/2008 στις 06:33
πηγή χρήστη

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