Вопрос по java, permutation – перестановки строки с использованием итерации

12

Я пытаюсь найти перестановку заданной строки, но я хочу использовать итерацию. Рекурсивное решение, которое я нашел в Интернете, и я его понимаю, но преобразование его в итеративное решение действительно не работает. Ниже я приложил свой код. Буду очень признателен за помощь:

public static void combString(String s) {
    char[] a = new char[s.length()];
    //String temp = "";
    for(int i = 0; i < s.length(); i++) {
        a[i] = s.charAt(i);
    }
    for(int i = 0; i < s.length(); i++) {
        String temp = "" + a[i];    

        for(int j = 0; j < s.length();j++) {
            //int k = j;
            if(i != j) {
                System.out.println(j);
                temp += s.substring(0,j) + s.substring(j+1,s.length());
            }               
        }
        System.out.println(temp);
    }
}
Пожалуйста, используйте тег домашней работы, если это школьная или университетская курсовая работа. Bobulous
я действительно пытаюсь, и я знаю, что мой код неверный .. не могу это исправить !! ueg1990
Вы хотите напечататьall перестановки строки? Это не ясно из вопроса. Petr Pudlák
Возможно, вы захотите посмотреть на ответы на этотrelated question Don Roby
пример, если у меня есть строка abc ... другие возможности: abc, acb, bac, bca, cab, cba ueg1990

Ваш Ответ

6   ответов
4
    List<String> results = new ArrayList<String>();
    String test_str = "abcd";
    char[] chars = test_str.toCharArray();
    results.add(new String("" + chars[0]));
    for(int j=1; j<chars.length; j++) {
        char c = chars[j];
        int cur_size = results.size();
        //create new permutations combing char 'c' with each of the existing permutations
        for(int i=cur_size-1; i>=0; i--) {
            String str = results.remove(i);
            for(int l=0; l<=str.length(); l++) {
                results.add(str.substring(0,l) + c + str.substring(l));
            }
        }
    }
    System.out.println("Number of Permutations: " + results.size());
    System.out.println(results);

если у нас есть 3 строки символов, например "abc", мы можем сформировать перестановки, как показано ниже.

1) создать строку с первым символом, например, & APOS; & APOS; и сохранить это в результатах.

    char[] chars = test_str.toCharArray();
    results.add(new String("" + chars[0]));

2) Теперь возьмите следующий символ в строке (т.е. "b") и вставьте его во все возможные позиции ранее созданных строк в результатах. Поскольку на данный момент у нас есть только одна строка результатов («a»), это дает нам 2 новые строки «ba», «ab». Вставьте эти недавно построенные строки в результаты и удалите & quot; a & quot ;.

    for(int i=cur_size-1; i>=0; i--) {
        String str = results.remove(i);
        for(int l=0; l<=str.length(); l++) {
            results.add(str.substring(0,l) + c + str.substring(l));
        }
    }

3) Повторите 2) для каждого символа в данной строке.

for(int j=1; j<chars.length; j++) {
    char c = chars[j];
     ....
     ....
}

Это дает нам «cba», «bca», «bac»; от "ba" и «кабина», «acb»; и "abc" от "ab"

@ Cyclotron3x3 вы пройдете 1 перестановку размера 1 в первой итерации, поэтому создайте 2 (= 2!) Перестановки, 2 перестановки во 2-й итерации размера 2, поэтому создайте 6 (= 3!) Перестановок, 6 перестановок размера 3 в 3-я итерация - создайте ^ * 4 = 24 = 4! перестановки .. и вообще к! перестановки для каждой итерации. последняя итерация будет перестановками размера n-1 - у вас есть (n-1)! из них вы можете добавить последний символ в n местах - так что n! для последней итерации. Таким образом, сложность будет O (Sum (k!) K = 1..n)
Пожалуйста, добавьте некоторые объяснения. Ответы только на код не очень полезны. Благодарю.
Добавлено пояснение к комментариям.
как обрабатывать случай, когда какой-то символ появляется более одного раза на входе?
@ Глубина в чем сложность этого алгоритма?
-1
// Java program to print all permutations of a
// given string.
public class Permutation
{
    public static void main(String[] args)
    {
        String str = "ABC";
        int n = str.length();
        Permutation permutation = new Permutation();
        permutation.permute(str, 0, n-1);
    }

    /**
     * permutation function
     * @param str string to calculate permutation for
     * @param s starting index
     * @param e end index
     */
    private void permute(String str, int s, int e)
    {
        if (s == e)
            System.out.println(str);
        else
        {
            for (int i = s; i <= s; i++)
            {
                str = swap(str,l,i);
                permute(str, s+1, e);
                str = swap(str,l,i);
            }
        }
    }

    /**
     * Swap Characters at position
     * @param a string value
     * @param i position 1
     * @param j position 2
     * @return swapped string
     */
    public String swap(String a, int i, int j)
    {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i] ;
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

}
Пожалуйста, добавьте описание того, что делает этот код, это ответ?
3

той проблемы.

static List<String> permutations(String string) {
    List<String> permutations = new LinkedList<>();
    Deque<WorkUnit> workQueue = new LinkedList<>(); 

    // We need to permutate the whole string and haven't done anything yet.
    workQueue.add(new WorkUnit(string, ""));

    while (!workQueue.isEmpty()) { // Do we still have any work?
        WorkUnit work = workQueue.poll();

        // Permutate each character.
        for (int i = 0; i < work.todo.length(); i++) {
            String permutation = work.done + work.todo.charAt(i);

            // Did we already build a complete permutation?
            if (permutation.length() == string.length()) {
                permutations.add(permutation);
            } else {

                // Otherwise what characters are left? 
                String stillTodo = work.todo.substring(0, i) + work.todo.substring(i + 1);
                workQueue.add(new WorkUnit(stillTodo, permutation));
            }
        }
    }
    return permutations; 
}

Вспомогательный класс для хранения частичных результатов очень прост.

/**
 * Immutable unit of work
 */
class WorkUnit {
    final String todo;
    final String done;

    WorkUnit(String todo, String done) {
        this.todo = todo;
        this.done = done;
    }
}

Вы можете проверить приведенный выше фрагмент кода, поместив их в этот класс.

import java.util.*;

public class AllPermutations {

    public static void main(String... args) {
        String str = args[0];
        System.out.println(permutations(str));
    }

    static List<String> permutations(String string) {
        ...
    }
}

class WorkUnit {
    ...
}

Попробуйте, скомпилировав и запустив.

$ javac AllPermutations.java; java AllPermutations abcd

Приведенную ниже реализацию также можно легко настроить, чтобы она возвращала список перестановок в обратном порядке, используя стек работы LI, FO вместо очереди FIFO.

0

import java.util.ArrayDeque;
import java.util.Queue;

public class PermutationIterative {
    public static void main(String[] args) {
        permutationIterative("abcd");
    }

    private static void permutationIterative(String str) {
        Queue<String> currentQueue = null;
        int charNumber = 1;
        for (char c : str.toCharArray()) {
            if (currentQueue == null) {
                currentQueue = new ArrayDeque<>(1);
                currentQueue.add(String.valueOf(c));
            } else {
                int currentQueueSize = currentQueue.size();
                int numElements = currentQueueSize * charNumber;
                Queue<String> nextQueue = new ArrayDeque<>(numElements);
                for (int i = 0; i < currentQueueSize; i++) {
                    String tempString = currentQueue.remove();
                    for (int j = 0; j < charNumber; j++) {
                        int n = tempString.length();
                        nextQueue.add(tempString.substring(0, j) + c + tempString.substring(j, n));
                    }
                }
                currentQueue = nextQueue;
            }
            charNumber++;
        }
        System.out.println(currentQueue);
    }
}
1
import java.util.List;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;

public class Anagrams{

    public static void main(String[] args)
    {

        String inpString = "abcd";
        Set<String> combs = getAllCombs(inpString);

        for(String comb : combs)
        {
            System.out.println(comb);
        }

    }


    private static Set<String> getAllCombs(String inpString)
    {
        Set<String> combs = new HashSet<String>();
        if( inpString == null | inpString.isEmpty())
            return combs;

        combs.add(inpString.substring(0,1));
        Set<String> tempCombs = new HashSet<String>();
        for(char a : inpString.substring(1).toCharArray())
        {
            tempCombs.clear();
            tempCombs.addAll(combs);
            combs.clear();
            for(String comb : tempCombs)
            {
                combs.addAll(getCombs(comb,a));
            }
        }
        return combs;
    }

    private static Set<String> getCombs(String comb, char a) {
        Set<String> combs = new HashSet<String>();
        for(int i = 0 ; i <= comb.length(); i++)
        {
            String temp = comb.substring(0, i) + a + comb.substring(i);
            combs.add(temp);
            //System.out.println(temp);
        }
        return combs;
    }   
}
Приятно, что это ваш первый пост. Добавить некоторые комментарии и / или объяснения того, что происходит .. Так что это на самом деле помогает другим ..
12

связанный вопрос комментарий, здесь реализация Java, которая делает то, что вы хотите, используяПодсчет алгоритма QuickPerm:

public static void combString(String s) {
    // Print initial string, as only the alterations will be printed later
    System.out.println(s);   
    char[] a = s.toCharArray();
    int n = a.length;
    int[] p = new int[n];  // Weight index control array initially all zeros. Of course, same size of the char array.
    int i = 1; //Upper bound index. i.e: if string is "abc" then index i could be at "c"
    while (i < n) {
        if (p[i] < i) { //if the weight index is bigger or the same it means that we have already switched between these i,j (one iteration before).
            int j = ((i % 2) == 0) ? 0 : p[i];//Lower bound index. i.e: if string is "abc" then j index will always be 0.
            swap(a, i, j);
            // Print current
            System.out.println(join(a));
            p[i]++; //Adding 1 to the specific weight that relates to the char array.
            i = 1; //if i was 2 (for example), after the swap we now need to swap for i=1
        }
        else { 
            p[i] = 0;//Weight index will be zero because one iteration before, it was 1 (for example) to indicate that char array a[i] swapped.
            i++;//i index will have the option to go forward in the char array for "longer swaps"
        }
    }
}

private static String join(char[] a) {
    StringBuilder builder = new StringBuilder();
    builder.append(a);
    return builder.toString();
}

private static void swap(char[] a, int i, int j) {
    char temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
@DonRoby: это отличное решение. Хотя я проследил это с помощью примера ввода, я не смог выяснить точную логику или то, как вы подошли к этой проблеме. Было бы полезно для нас, если бы вы могли объяснить нам, как вы это решили. Благодарю.
Пожалуйста, объясните логику @DonRoby
Это слишком сложно, если вы можете придумать более простое решение. Делать это сложнее итеративно, чем рекурсивно.
Используемый здесь Stringbuilder просто преобразует массив char обратно в строку.
не слишком ли это сложно? ueg1990

Похожие вопросы