Określona permutacja elementów w tablicy znaków w języku JAVA?

Question

Jak mogę wyświetlić wszystkie permutacje wielkich/małych liter dla dowolnej litery określonej w tablicy znaków? Powiedzmy, że mam tablicę takich znaków jak: ['h', 'e', ​​'l', 'l', 'o'] i chciałem wydrukować możliwe kombinacje dla powiedzenia litery "l" więc wydrukuje [helo, heLlo, heLLo, helLo].

To jest to, co do tej pory miałem (jedynym problemem jest to, że mogę wydrukować permutacje, ale nie jestem w stanie wydrukować ich wewnątrz rzeczywistego słowa, więc mój kod wypisuje [ll, lL, LL, LL] zamiast z powyższego przykładu

mój kod:...

import java.util.ArrayList; 
import java.util.HashSet; 

public class Main { 

public static void main(String[] args) { 
    //Sample Word 
    String word = "Tomorrow-Today"; 

    //Sample Letters for permutation 
    String rule_char_set = "tw"; 


    ArrayList<Character> test1 = lettersFound(word, rule_char_set); 

    printPermutations(test1); 







} 

public static void printPermutations(ArrayList<Character> arrayList) { 
    char[] chars = new char[arrayList.size()]; 
    int charIterator = 0; 

    for(int i=0; i<arrayList.size(); i++){ 
     chars[i] = arrayList.get(i); 
    } 

    for (int i = 0, n = (int) Math.pow(2, chars.length); i < n; i++) { 
     char[] permutation = new char[chars.length]; 
     for (int j =0; j < chars.length; j++) { 
      permutation[j] = (isBitSet(i, j)) ? Character.toUpperCase(chars[j]) : chars[j]; 
     } 
     System.out.println(permutation); 
    } 
} 

public static boolean isBitSet(int n, int offset) { 
    return (n >> offset & 1) != 0; 
} 

public static ArrayList<Character> lettersFound(String word, String rule_char_set) { 

    //Convert the two parameter strings to two character arrays 
    char[] wordArray = word.toLowerCase().toCharArray(); 
    char[] rule_char_setArray = rule_char_set.toLowerCase().toCharArray(); 

    //ArrayList to hold found characters; 
    ArrayList<Character> found = new ArrayList<Character>(); 

    //Increments the found ArrayList that stores the existent values. 
    int foundCounter = 0; 


    for (int i = 0; i < rule_char_setArray.length; i++) { 
     for (int k = 0; k < wordArray.length; k++) { 
      if (rule_char_setArray[i] == wordArray[k]) { 
       found.add(foundCounter, rule_char_setArray[i]); 
       foundCounter++; 

      } 
     } 
    } 
    //Convert to a HashSet to get rid of duplicates 
    HashSet<Character> uniqueSet = new HashSet<>(found); 

    //Convert back to an ArrayList(to be returned) after filtration of duplicates. 
    ArrayList<Character> filtered = new ArrayList<>(uniqueSet); 

    return filtered; 
} 

} 

Answer 1

Sanket Makani odpowiedź jest doskonały.

Mogę zaoferować bardziej obiektywne podejście do tego problemu.

Jako dane wejściowe masz ciąg do modyfikacji i znaki, które należy zastąpić zmienionym wielkością liter (górnym lub dolnym). Jako wynik otrzymasz wszystkie permutowane łańcuchy.

Chciałbym stworzyć strukturę, która zawiera indeks i możliwe wartości zmienić z:

class Change { 
int index; 
char values[]; 
} 

Musimy dołożyć wszelkich możliwych kombinacji, więc pozwala to pole, które pokaże, który znak jest obecnie stosowany w celu Nasza struktura i dodać kilka metod:

class Change { 
int index; 
char values[]; 
int cur; 

void reset() {cur=0;} 
boolen isMax(){return cur==values.length-1;} 
void next(){cur++;} 
char getValue(){ return values[cur]; } 
} 

będziemy mieć listę lub tablicę tych klas następnie, które stawiamy do osobnej klasy

class Combination { 
Change changes[]; 

    void reset() { for (Change c: changes) c.reset();} 

    boolean next() { 
    for (int i=0; i<changes.length; i++) 
     if (changes[i].isMax()) 
     changes[i].reset(); // next change will be taken in cycle, with "next()" 
     else {changes[i].next(); return true;} 

    return false; // all changes are max 
    } 
} 

Tak więc, po zainicjowaniu klasy "Kombinacja" danymi wejściowymi, można użyć jej w cyklu.

Combination c = new Combination(); 
.... // initialization here 
c.reset(); 
do { 
... // update and print your string 
} while (c.next() ); 

Inicjalizacja „kombinacja” i przy użyciu wartości dla aktualizacji ciąg wejściowy wyjadę po ciebie :)

Answer 2

musisz zrobić kilka zmian w programie Twoja logika jest doskonały, że trzeba znaleźć najpierw characters być zmieniane w danym słowie Po znajdując je, znajdź powerset z characters, aby wydrukować całą permutację, ale to tylko wydrukuje permuatation znaków z rule-char-set, które są obecne w podanym słowie.

Kilka zmian, które musisz wprowadzić, to najpierw znaleźć wszystkie indexes z word, które zawierają znaki rule-char-set. Następnie znajdź wszystkie subsets indeksów przechowywanych w ArrayList, a następnie dla każdego elementu każdego z podzbiorów, ustaw character na tej index na wielką literę, która da ci wszystkie wymagane permutation.

Rozważmy przykład, że word = "Hello" i rule-char-set="hl" Potem tu najpierw trzeba znaleźć wszystkie indeksy h i l w ciągu word.

Oto indeksy: 0,2,3. Zapisz go pod numerem ArrayList, a następnie znajdź jego powerset. Następnie dla każdego subset, zmień character na tę index na literę uppercase.

Word[] = {'h','e','l','l','o'} 
indexes = 0 , 1 , 2 , 3 , 4 


index[]= { 0 , 2 ,3} //Store the indexes of characters which are to be changed 


BITSET  |  SUBSET  |  word 

000   |   -   |  hello 
001   |  {3}  |  helLo 
010   |  {2}  |  heLlo 
011   |  {2,3}  |  heLLo 
100   |  {0}  |  Hello 
101   |  {0,3}  |  HelLo 
110   |  {0,2}  |  HeLlo 
111   |  {0,2,3}  |  HeLLo 

Kod:

import java.util.ArrayList; 
import java.util.HashSet; 

public class Main { 

    public static void main(String[] args) { 
     //Sample Word 
     String word = "Tomorrow-Today"; 

     //Sample Letters for permutation 
     String rule_char_set = "tw"; 


     ArrayList<Integer> test1 = lettersFound(word, rule_char_set); //To store the indexes of the characters 

     printPermutations(word,test1); 

    } 

    public static void printPermutations(String word,ArrayList<Integer> arrayList) { 
     char word_array[]=word.toLowerCase().toCharArray(); 
     int length=word_array.length; 
     int index[]=new int[arrayList.size()]; 

     for(int i=0; i<arrayList.size(); i++){ 
      index[i] = arrayList.get(i); 
     } 

     for (int i = 0, n = (int) Math.pow(2, index.length); i < n; i++) { 
      char[] permutation = new char[length]; 

      System.arraycopy(word_array,0,permutation,0,length);  

      //First copy the original array and change 
      //only those character whose indexes are present in subset 

      for (int j =0; j < index.length; j++) { 
       permutation[index[j]] = (isBitSet(i, j)) ? Character.toUpperCase(permutation[index[j]]) : permutation[index[j]]; 
      } 
      System.out.println(permutation); 
     } 
    } 

    public static boolean isBitSet(int n, int offset) { 
     return (n >> offset & 1) != 0; 
    } 

    public static ArrayList<Integer> lettersFound(String word, String rule_char_set) { 

     //Convert the two parameter strings to two character arrays 
     char[] wordArray = word.toLowerCase().toCharArray(); 
     char[] rule_char_setArray = rule_char_set.toLowerCase().toCharArray(); 

     //ArrayList to hold found characters; 
     ArrayList<Integer> found = new ArrayList<Integer>(); 

     //Increments the found ArrayList that stores the existent values. 
     int foundCounter = 0; 


     for (int i = 0; i < rule_char_setArray.length; i++) { 
      for (int k = 0; k < wordArray.length; k++) { 
       if (rule_char_setArray[i] == wordArray[k]) { 
        found.add(foundCounter, k);  //Store the index of the character that matches 
        foundCounter++; 

       } 
      } 
     } 
     return found; 
    } 

} 

wyjściowa:

tomorrow-today 
Tomorrow-today 
tomorrow-Today 
Tomorrow-Today 
tomorroW-today 
TomorroW-today 
tomorroW-Today 
TomorroW-Today 

Answer 3

dla przypadku permutacji, myślę rekurencji jest najlepiej dopasowana pod względem czytelności, biorąc pod uwagę, że być może nie jest najlepszy pod względem wydajności.

Moje podejście byłoby to:

public static void main(String[] args) { 
    generateCombinations("hello", "l", ""); 
} 

public static void generateCombinations(String text, String changingLetters, String current) { 
    if (0 == text.length()) { 
     System.out.println(current); 
     return; 
    } 
    String currentLetter = text.substring(0, 1); 
    if (changingLetters.contains(currentLetter)) { 
     generateCombinations(text.substring(1), changingLetters, current + currentLetter.toUpperCase()); 
    } 
    generateCombinations(text.substring(1), changingLetters, current + currentLetter); 
} 

Wyjście do głównej realizacji będą:

heLLo 
heLlo 
helLo 
hello