Умный способ генерации перестановок и комбинации String

Ответ 1

Вы должны проверить этот ответ: Получение каждой возможной перестановки строки или комбинации, включая повторяющиеся символы в Java

Чтобы получить этот код:

public static String[] getAllLists(String[] elements, int lengthOfList)
{
    //initialize our returned list with the number of elements calculated above
    String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

    //lists of length 1 are just the original elements
    if(lengthOfList == 1) return elements; 
    else {
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);

        //append the sublists to each element
        int arrayIndex = 0;

        for(int i = 0; i < elements.length; i++){
            for(int j = 0; j < allSublists.length; j++){
                //add the newly appended combination to the list
                allLists[arrayIndex] = elements[i] + allSublists[j];
                arrayIndex++;
            }
        }
        return allLists;
    }
}

public static void main(String[] args){
    String[] database = {"a","b","c"};
    for(int i=1; i<=database.length; i++){
        String[] result = getAllLists(database, i);
        for(int j=0; j<result.length; j++){
            System.out.println(result[j]);
        }
    }
}

Хотя дальнейшее улучшение памяти может быть сделано, так как это решение генерирует все решения для памяти сначала (массив), прежде чем мы можем его распечатать. Но идея та же, что и для использования рекурсивного алгоритма.

Ответ 2

Это пахнет подсчетом в двоичном формате:

• 001
• 010
• 011
• 100
• 101
• ...

Моим первым инстинктом было бы использовать двоичный счетчик как "растровое изображение" символов для генерации тех возможных значений. Тем не менее, есть несколько замечательных ответов на связанные вопросы здесь, которые предполагают использование рекурсии. См

• Как сделать этот метод/метод перестановок рекурсивным?
• Узнайте все комбинации и перестановки - Java
• перестановки строк в java и поиск комбинаций
• http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

Ответ 3

Java-реализация вашего генератора перестановок: -

public class Permutations {


    public static void permGen(char[] s,int i,int k,char[] buff) {
        if(i<k) {
            for(int j=0;j<s.length;j++) {

                buff[i] = s[j];
                permGen(s,i+1,k,buff);
            }
        }       
        else {

         System.out.println(String.valueOf(buff)); 

        }

    }

    public static void main(String[] args) {
        char[] database = {'a', 'b', 'c'};
        char[] buff = new char[database.length];
        int k = database.length;
        for(int i=1;i<=k;i++) {
            permGen(database,0,i,buff);
        }

}

}

Ответ 4

Хорошо, поэтому лучшим решением для перестановок является рекурсия. Скажем, у вас было n разных букв в строке. Это приведет к появлению n подпроцессов, по одному для каждого набора перестановок, начиная с каждой уникальной буквы. Создайте метод permutationsWithPrefix(String thePrefix, String theString), который будет решать эти индивидуальные проблемы. Создайте другой метод listPermutations(String theString), реализация будет чем-то вроде

void permutationsWithPrefix(String thePrefix, String theString) {
   if ( !theString.length ) println(thePrefix + theString);
   for(int i = 0; i < theString.length; i ++ ) {
      char c = theString.charAt(i);
      String workingOn = theString.subString(0, i) + theString.subString(i+1);   
      permutationsWithPrefix(prefix + c, workingOn);
   }
} 

void listPermutations(String theString) {
   permutationsWithPrefix("", theString);
}

Ответ 5

Я столкнулся с этим вопросом как один из вопросов интервью. Ниже приведено решение, которое я реализовал для этой проблемы с помощью рекурсии.

public class PasswordCracker {

private List<String> doComputations(String inputString) {

    List<String> totalList =  new ArrayList<String>();
    for (int i = 1; i <= inputString.length(); i++) {

        totalList.addAll(getCombinationsPerLength(inputString, i));
    }
    return totalList;

}

private ArrayList<String> getCombinationsPerLength(
        String inputString, int i) {

    ArrayList<String> combinations = new ArrayList<String>();

    if (i == 1) {

        char [] charArray = inputString.toCharArray();
        for (int j = 0; j < charArray.length; j++) {
            combinations.add(((Character)charArray[j]).toString());
        }
        return combinations;
    }
    for (int j = 0; j < inputString.length(); j++) {

        ArrayList<String> combs = getCombinationsPerLength(inputString, i-1);
        for (String string : combs) {
            combinations.add(inputString.charAt(j) + string);
        }
    }

    return combinations;
}
public static void main(String args[]) {

    String testString = "abc";
    PasswordCracker crackerTest = new PasswordCracker();
    System.out.println(crackerTest.doComputations(testString));

}
}

Ответ 6

Для тех, кто ищет нерекурсивные параметры, вот пример для числовых перестановок (можно легко адаптировать к char. numberOfAgents - количество столбцов, а набор чисел - от 0 до numberOfActions

    int numberOfAgents=5;
    int numberOfActions = 8;
    byte[][]combinations = new byte[(int)Math.pow(numberOfActions,numberOfAgents)][numberOfAgents];

    // do each column separately
    for (byte j = 0; j < numberOfAgents; j++) {
        // for this column, repeat each option in the set 'reps' times
        int reps = (int) Math.pow(numberOfActions, j);

        // for each column, repeat the whole set of options until we reach the end
        int counter=0;
        while(counter<combinations.length) {
            // for each option
            for (byte i = 0; i < numberOfActions; i++) {
                // save each option 'reps' times
                for (int k = 0; k < reps; k++)
                    combinations[counter + i * reps + k][j] = i;
            }
            // increase counter by 'reps' times amount of actions
            counter+=reps*numberOfActions;
        }
    }

    // print
    for(byte[] setOfActions : combinations) {
        for (byte b : setOfActions)
            System.out.print(b);
        System.out.println();
    }

Ответ 7

// 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!!