Wednesday, March 20, 2019

Returning the permutation of the string to find the number just greater number formed by the given digits in java

Problem:

Find the number  just greater than given number  which is formed by the available digits?

eg. if number is 86435, the number just greater than 86435 must be 86453.

Solution1:

public class QuestionB {
    public static ArrayList<String> getPerms(String remainder) {
        int len = remainder.length();
        ArrayList<String> result = new ArrayList<String>();

        /* Base case. */        if (len == 0) {
            result.add(""); // Be sure to return empty string!  
          return result;
        }


        for (int i = 0; i < len; i++) {
            /* Remove char i and find permutations of remaining characters.*/   
         String before = remainder.substring(0, i);
            String after = remainder.substring(i + 1, len);
            ArrayList<String> partials = getPerms(before + after);

            /* Prepend char i to each permutation.*/        
            for (String s : partials) {
                result.add(remainder.charAt(i) + s);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        ArrayList<String> list = getPerms("abc");
        System.out.println("There are " + list.size() + " permutations.");
        for (String s : list) {
            System.out.println(s);
        }
    }

}

Solution2:

public class GeneralizedSolution {
  public static void main(String[] args) {
    String s = "86435";
//    System.out.println("\nString " + s + ":\nPermutations: " + Permutation(s)); 
 Set<Integer> set = Permutation(s).stream().map(a -> Integer.parseInt(a))
.collect(Collectors.toSet());
    List<Integer> list = new ArrayList<>(set);
    Collections.sort(list);
//    System.out.println(list);    int index = list.indexOf(Integer.parseInt(s));
    if (index == list.size() - 1) {
      System.out.println("there is no number greatet than " + s);
    } else {
      System.out.println("The number just greater than " + s + "is :" + list.get(index + 1));

    }
  }

  public static Set<String> Permutation(String str) {
    Set<String> Result = new HashSet<String>();
    if (str == null) {
      return null;
    } else if (str.length() == 0) {
      Result.add("");
      return Result;
    }

    char firstChar = str.charAt(0);
    String rem = str.substring(1);
    Set<String> words = Permutation(rem);
    for (String newString : words) {
      for (int i = 0; i <= newString.length(); i++) {
        Result.add(CharAdd(newString, firstChar, i));
      }
    }
    return Result;
  }

  public static String CharAdd(String str, char c, int j) {
    String first = str.substring(0, j);
    String last = str.substring(j);
    return first + c + last;
  }

}


solution 3rd:
of permutation with finding permutation with making first element constant and
finding permutation of remaining:


class Permutations
{
 // Recursive function to generate all permutations of a String
 private static void permutations(String candidate, String remaining)
 {
  if (remaining.length() == 0) {
   System.out.println(candidate);
  }

  for (int i = 0; i < remaining.length(); i++)
  {
   String newCandidate = candidate + remaining.charAt(i);

   String newRemaining = remaining.substring(0, i) +
          remaining.substring(i + 1);

   permutations(newCandidate, newRemaining);
  }
 }

 // Find Permutations of a String in Java
 public static void main(String[] args)
 {
  String s = "ABC";
  permutations("", s);
 }
}

No comments:

Post a Comment