Algorithme pour générer toutes les combinaisons d'une chaîne

J'ai trouvé un lien sur internet qui montre un algorithme permettant de générer toutes les combinaisons d'une chaîne: http://www.mytechinterviews.com/combinations-of-a-string

Algorithme est copié ci-dessous.

void combine(String instr, StringBuffer outstr, int index)
{
    for (int i = index; i < instr.length(); i++)
    {
        outstr.append(instr.charAt(i));
        System.out.println(outstr);
        combine(instr, outstr, i + 1);
        outstr.deleteCharAt(outstr.length() - 1);
    }
} 

combine("abc", new StringBuffer(), 0);

Ce que je ne comprends pas, c'est la ligne:

outstr.deleteCharAt(outstr.length() - 1);

Si je supprime cette ligne, le programme de toute évidence ne fonctionne plus, mais pourquoi est-ce nécessaire en premier lieu? Je comprends le récursive idée de l'endroit où nous faisons varier d'un caractère de début et de manière récursive sur les autres personnages, mais le deleteChar ligne ne semblent pas correspondre logiquement n'importe où. Quelle était la raison de l'ajout de la outstr.deleteCharAt ligne?

source d'informationauteur john | 2012-01-23

7

L'appel de outstr.deleteCharAt compteurs de l'effet de outstr.append par la suppression du dernier caractère de la outstr.

Chaque itération de boucle se déroule comme suit:
1. ajouter un caractère
2. imprimer le résultat
3. effectuer un appel récursif au niveau i+1
4. supprimer le caractère, nous avons ajouté à l'étape 1
26

Façon la plus simple de calculer les combinaisons possibles des chaînes est ici ...

Mathématiquement pour trouver la R de combinaisons dans un lot de N = Rcn

Donc, ce que nous trouvons ici, c'est que toutes les combinaisons possibles = Nc0 + Nc1 .... + Ncn = 2 Pow N

Ainsi, vous obtenez 2 Pow N combinaisons de mot de longueur N caractères.

Si vous représenter 1 à 2 Pow N des entiers en binaire, et le lieu de votre personnage à l'endroit où 1 est présent, enfin, vous obtiendrez la solution.

Exemple:

D'entrée : ABC

Solution :

ABC longueur est de 3. Tellement de combinaisons possibles de 2 Pow 3 = 8

Si 0 - 8 représenté en binaire

000 =

001 = C

010 = B

011 = BC

100 = Un

101 = AC

110 = AB

111 = ABC

toutes les combinaisons possibles sont indiquées ci-dessus.
4

Soldes la première ligne du corps de la boucle, de la restauration outstr à ce qu'il était dans le haut du corps de la boucle (en enlevant le caractère de l'instrument qui a été ajouté).
3

Il s'adapte très logiquement. Vous voyez ce que nous avons ici est un algorithme récursif. À chaque étape de position i nous a mis une lettre de la chaîne, puis appeler la fonction récursive pour mettre une autre lettre sur la position suivante. Cependant, quand nous serons de retour à partir de la récursivité, nous avons besoin de supprimer le caractère nous mettons d'abord, de sorte que nous pouvons le remplacer par la suivante dans la séquence. Exemple:
```
append a on pos 0 -> a
call recursion
append a on pos 1 -> aa
call recursion
append a on pos 2 -> aaa
return from recursion
remove a from pos 2 -> aa
append b on pos 2 -> aab
return from recursion
remove b from pos 2 -> aa
append c on pos 2 -> aac
etc.
```

Code ci-dessous est de générer de permutation et de combinaison de chaîne, fondamentalement, le concept est de choisir un caractère à la fois:

public class permutecombo
{
  static void initiate(String s)
  {
    permute("", s);
    System.out.println("----------------------------------------- ");
    combo("", s);
    System.out.println("----------------------------------------- ");
  }

  static void combo(String prefix, String s)
  {
    int N = s.length();

    System.out.println(prefix);

    for (int i = 0 ; i < N ; i++)
      combo(prefix + s.charAt(i), s.substring(i+1));
  }
  static void permute(String prefix, String s)
  {
    int N = s.length();

    if (N == 0)
      System.out.println(" " + prefix);

    for (int i = 0 ; i < N ; i++)
      permute(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
  }

  public static void main(String[] args)
  {
    String s = "1234";
    initiate(s);
  }
}

1
```
outstr.deleteCharAt(outstr.length() - 1); 
```
signifie que vous avez
```
n^(n-1)/2 pairs of combinations.
```
L'itération de la boucle ne s'arrête pas après la fonction récursive appeler si vous avez besoin d'effacer le dernier caractère dans le tampon de sortie parce que vous ne voulez pas d'obtenir
```
n^n/2 pairs of combinations.
```
Dans un graphe théorie, il serait un court-circuit.

Voici le code C++ sans le difficile retour en arrière étape OP question.

#include <iostream>
#include <string>
using namespace std;
static const string in("abc");
void combine(int i, string out)
{
    if (i==in.size()) {
        cout << out << endl;
        return;
    }
    combine(i+1, out);
    combine(i+1, out+in[i]);
}

int main()
{
    combine(0, "");
    return 0;
}

J'espère que cela reflète mieux l'esprit de combinaisons.

Nous pouvons générer tous les sous-chaînes d'une chaîne en utilisant les bits concept qui a été mentionné précédemment. Voici le code (en C++ , mais vous voyez l'idée) pour ce faire : -

string s;
int n = s.size();
int num = 1<<n;
for(int i =1; i< num ; i++){ //Checks all the permutations.
    int value = i;
    int j, pos;
    for (j=1, pos=1; j < num; j<<=1, pos++) //Finds the bits that are set
        if (i & j)
            cout<<s[pos-1]; //You can print s[n-pos] to print according to bit position
    cout<<endl;        
}

Par exemple;- String s = abc ,

 The size is 3  . So we check from 1 to 7 ( 1<<3).
 for i = 1 ( 001 ) , the first bit is set, so a is printed.
 for i = 2 ( 010 ) , the second bit is set, so b is printed.
 for i = 3 ( 011 ) , the first and second bit are set, so ab is printed.
 .
 .
 .
 for i = 7 ( 111 ) , all three bits are set, so abc is printed.

//IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!
import java.util.*;
public class Permutation {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
System.out.println("ENTER A STRING");
Set<String> se=find(in.nextLine());
System.out.println((se));
}
public static Set<String> find(String s)
{
Set<String> ss=new HashSet<String>();
if(s==null)
{
return null;
}
if(s.length()==0)
{
ss.add("");
}
else
{
char c=s.charAt(0);
String st=s.substring(1);
Set<String> qq=find(st);
for(String str:qq)
{
for(int i=0;i<=str.length();i++)
{
ss.add(comb(str,c,i));
}
}
}
return ss;
}
public static String comb(String s,char c,int i)
{
String start=s.substring(0,i);
String end=s.substring(i);
return start+c+end;
}
}
//IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

Vous devez vous connecter pour publier un commentaire.

Exemple: