Permutations

kata programming

مساله:

در این کاتا شما باید تمام جایگشت های رشته ای که از ورودی می گیرید را ایجاد کنید و آنهایی که تکراری هستند را پاک کنید.

Description:

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

Examples:

Permutations.singlePermutations("a") `shouldBe` ["a"]
Permutations.singlePermutations("ab") `shouldBe` ["ab", "ba"]
Permutations.singlePermutations("aabb") `shouldBe` ["aabb","abab","abba","baab","baba","bbaa"]

The order of the permutations doesn’t matter.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Permutations {
    
    public static List<String> list = new ArrayList<String>();
  
    public static List<String> singlePermutations(String s) {
      list = new ArrayList<String>();
      singlePermutations("", s);
      Collections.sort(list);
      return list;
    }

    private static void singlePermutations(String prefix, String str) {
      int n = str.length();
      if (n == 0) {
        if (!list.contains(prefix))
          list.add(prefix);
      } else {
        for (int i = 0; i < n; i++)
          singlePermutations(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
      }
    }
}
import java.util.*;

class Permutations {
    
    public static void generate(String seq, String out, List<String> list){
        if (seq.isEmpty()){
            if (!list.contains(out))
                list.add(out);
        }
        else
            for(int i=0; i < seq.length(); i++)
                generate(remove(seq,i), out+seq.charAt(i), list);
    }
    
    public static String remove(String str, int idx){
        return str.substring(0, idx)+str.substring(idx+1);
    }
    
    public static List<String> singlePermutations(String s) {
        List<String> list = new ArrayList<>();
        for(int i=0; i < s.length(); i++){
            generate(remove(s,i), ""+s.charAt(i), list);
        }
        return list;
    }
}
import static java.util.Collections.singletonList;
import static java.util.stream.Collectors.toList;

import java.util.List;

class Permutations {

  public static List<String> singlePermutations(final String s) {
    return permute("", s);
  }

  private static List<String> permute(final String prefix, final String s) {
  
    return s.isEmpty()
        ? singletonList(prefix)
        : s.chars()
            .distinct()
            .mapToObj(i -> (char) i)
            .map(c -> permute(prefix + c, takeOut(s, c)))
            .flatMap(List::stream)
            .collect(toList());
  }

  static String takeOut(final String s, final char c) {
    final int i = s.indexOf(c);
    return s.substring(0, i) + s.substring(i + 1);
  }
}
import java.util.*;

class Permutations {

    private static Set<String> perms;
    
    private static void swap(char[] arr, int i, int j) {
      char aux = arr[i];
      arr[i] = arr[j];
      arr[j] = aux;
    }
    
    private static void perm(char[] arr, int index) {
      if(index == arr.length) {
        perms.add(new String(arr));
      } else {
        for(int i=index;i<arr.length;i++) {
          swap(arr, index, i);
          perm(arr, index+1);
          swap(arr, index, i);
        }
      }
    }
    
    public static List<String> singlePermutations(String s) { 
        perms = new HashSet<>();
        perm(s.toCharArray(), 0);
        return new LinkedList<>(perms);
    }
}
import java.util.*;

class Permutations {
    
    public static List<String> singlePermutations(String s) {
        
        // Your code here!
        return permutate("",s,new ArrayList<String>());
    }
    public static List<String> permutate(String permute, String s, List<String> listed) {
      if (s.isEmpty() &&  !listed.contains(permute + s)) {
        listed.add(permute + s);
      } else {
        for (int i = 0; i < s.length(); i++) {
          permutate(permute + s.charAt(i), s.substring(0,i) + s.substring(i+1,s.length()), listed);
        }
      }
      return listed;
    }
}
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

class Permutations {
    
    public static List<String> singlePermutations(String s) {
        Set<String> set = new HashSet<>();
        if (s.length() == 1) {
            set.add(s);
        } else {
            for (int i = 0; i < s.length(); i++) {
                List<String> temp = singlePermutations(s.substring(0, i) + s.substring(i + 1));
                for (String string : temp) {
                    set.add(s.charAt(i) + string);
                }
            }
        }

        return new ArrayList<>(set);
    }
}

دیدگاهتان را بنویسید