Я пытаюсь найти ранг заданных строк с помощью рекурсии - PullRequest
Новая
       16

Я пытаюсь найти ранг заданных строк с помощью рекурсии

1 голос
/ 24 марта 2020

Я пытаюсь найти ранг заданных строк с помощью рекурсии, но, похоже, не могу выйти из рекурсии так, как я хочу. Куда я иду не так? 

    class Solution {
    public static int flag=0;
    public static int ans=0;
    public static int findRank(String A) {
      /* write your solution here */
      char[] carr=A.toCharArray();
      Arrays.sort(carr);
      String suffix=new String(carr);
      ArrayList<String> list=new ArrayList<String>();
          int rank=0;
      rank=generate(rank,"",suffix,list,A);

      for(int i=0;i<list.size();i++)
        System.out.print(list.get(i)+" ");

       return rank;
     }

    public static int generate(int rank,String prefix,String suffix, ArrayList<String> list,String A){
        if(suffix.length()==0){
            list.add(prefix);
            rank++; 
            if(prefix.equals(A)){

                return rank;
            }
        }

        for(int i=0;i<suffix.length();i++) {
          //  System.out.println(rank);
          return generate(rank,prefix+suffix.charAt(i),suffix.substring(0,i)+suffix.substring(i+1),list, A); 
        }

        return rank;
    }
}

Это вопрос: По заданной строке найдите ранг строки среди ее перестановок, отсортированных по лексикографическому признаку. Предположим, что никакие символы не повторяются.

Пример:

Входные данные: 'acb' Выходные данные: 2 Порядковые перестановки с буквами 'a', 'c' и 'b':

abc acb bac bca cab cba

Я попытался поместить его в визуализатор, вот код для этого: 

    import java.util.*;
public class Solution {
    public static int flag=0;
    public static int ans=0;
  public static void main(String args[]) {
      /* write your solution here */
     String A="dbca";
      char[] carr=A.toCharArray();
      Arrays.sort(carr);
      String suffix=new String(carr);
      ArrayList<String> list=new ArrayList<String>();
          int rank=0;
      rank=generate(rank,"",suffix,list,A);

      for(int i=0;i<list.size();i++)
        System.out.print(list.get(i)+" ");

       System.out.println(rank);

  }

    public static int generate(int rank,String prefix,String suffix, ArrayList<String> list,String A){
        if(suffix.length()==0){
            list.add(prefix);
            rank++;
            if(prefix.equals(A)){

                return rank;
            }

        }

            for(int i=0;i<suffix.length();i++){
              //  System.out.println(rank);
                   return generate(rank,prefix+suffix.charAt(i),suffix.substring(0,i)+suffix.substring(i+1),list, A);

            }

        return rank;
    }
}

https://cscircles.cemc.uwaterloo.ca/java_visualize/#mode = edit

1 Ответ

0 голосов
/ 24 марта 2020

Ваше значение для l oop заставляет вас завершить рекурсию после того, как вы найдете первую перестановку, поэтому вы всегда возвращаете 1.

Что вам следует сделать, это завершить рекурсию, как только вы найдете перестановка, которую вы ищете. Вы можете сделать это, например, если ваш рекурсивный метод возвратит флаг boolean вместо int.

Как только рекурсивный метод вернется, длина вашего list будет рангом, который вы ищем: 

public static int findRank(String A) 
{
    char[] carr=A.toCharArray();
    Arrays.sort(carr);
    String suffix=new String(carr);
    ArrayList<String> list=new ArrayList<String>();
    generate("",suffix,list,A);
    for(int i=0;i<list.size();i++)
        System.out.print(list.get(i)+" ");

     return list.size();
}

public static boolean generate(String prefix,String suffix, ArrayList<String> list,String A)
{
    if(suffix.length()==0){
        list.add(prefix);
        return (prefix.equals(A));
    }

    for(int i=0;i<suffix.length();i++) {
        if (generate(prefix+suffix.charAt(i),suffix.substring(0,i)+suffix.substring(i+1),list, A)) {
            return true;
        }
    }

    return false;
}
...