Strings: Нахождение всех перестановок символов из N знаков

 
 
 
Сообщения:1688
Пример показывает как просто можно реализовать алгоритм нахождения всех перестановок (длиной от 1 до кол-ва символов) набора любых символов, используя функцию toString(int radix) класса BigInteger.
import java.math.BigInteger;

public class PermutationsExample {

    public static void main(String[] args) {
       String str = "abcd";
       String[] allPermutations = permutations(str);
       for (String perm : allPermutations) {
          System.out.println(perm);
       }
    }

    /**
     *  Returns all permutations of characters in given string.
     *  s - string of max length FFFF
     */
    public static String[] permutations(String s) {
       int len = s.length();
       if (s == null || len == 0)
          throw new IllegalArgumentException("String is empty");
          
       int count = permutationCount(s);
       String[] result = new String[count];
      
       int k = 0; // length (count of characters) of current permutation
       int t = 0;
       for (int i = 0; i < count; i++, t++) {
          if (t % Math.pow(len, k) == 0) {
             k++;
             t = 0;
          }
          result[i] = valueToString(s, i, k);
       }
       return result;
    }

    /**
     * Returns count of all possible permutations of characters of given string. Used formula: SUM((N^i), i={1; N}), where N - length of string s.
     */
    public static int permutationCount(String s) {
       if (s == null || s.length() == 0)
          throw new IllegalArgumentException("String is empty");

       int result = 0;
       int len = s.length();
      
       if (len == 2) {
          result = 4;
       } else {
          for (int i = 1; i <= len; i++) {
             result += Math.pow(len, i);
          }
       }
       return result;
    }

    /**
     * Translates given int value to string of characters taken from set represented by chars string.
     */
    private static String valueToString(String chars, int val, int outLength) {
       // Translate number in M-scale of notation to string representation, M - chars.length()
       // Gotten string will consist of position numbers of characters in chars set
       String valS = BigInteger.valueOf(val).toString(chars.length()); // Ключевой вызов алгоритма

       // Cut beginning redundant characters (usually only 1)
       if (valS.length() > outLength) {
          valS = valS.substring(valS.length() - outLength);
       }

       StringBuffer resultBuf = new StringBuffer();
       for (int i = 0; i < valS.length(); i++) {
          resultBuf.append(chars.charAt(toPos(valS.charAt(i))));
       }
       return resultBuf.toString();
    }

    private static int toPos(char c) {
       return c - ZERO_CHAR;
    }

    private static final char ZERO_CHAR = new Character('0').charValue();
 }


Примечание
Код - Java 1.5
 
 
Сообщения:208
Спасибо дружище что код выложил!
 
 
Сообщения:208
Добавлю тогда сюда чуть чуть модифицированную версию где на вход подается список объектов. Может кому пригодится.
public  class  Permutations {
    /**
     *  Returns all permutations of characters in given string.
     *  s - string of max length FFFF
     */
    public  <T extends Object>  Set<Set<T>> permutations(List<T> words) {
        if (Util.getInstance().isEmpty(words) )
            throw new IllegalArgumentException("String is empty");

        int len = words.size();
        int count = permutationCount(words);
        Set<Set<T>> result = new HashSet<Set<T>>();

        int k = 0; // length (count of characters) of current permutation
        int t = 0;
        for (int i = 0; i < count; i++, t++) {
            if (t % Math.pow(len, k) == 0) {
                k++;
                t = 0;
            }
            result.add(valueToString(words, i, k));
        }
        return result;
    }

    /**
     * Returns count of all possible permutations of characters of given string. Used formula: SUM((N^i), i={1; N}), where N - length of string s.
     */
    private <T extends Object>  int permutationCount(List<T> words) {
        if (Util.getInstance().isEmpty(words))
            throw new IllegalArgumentException("String is empty");

        int result = 0;
        int len = words.size();

        if (len == 2) {
            result = 4;
        } else {
            for (int i = 1; i <= len; i++) {
                result += Math.pow(len, i);
            }
        }
        return result;
    }

    /**
     * Translates given int value to string of characters taken from set represented by chars string.
     */
    private <T extends Object>  Set<T> valueToString(List<T> words, int val, int outLength) {
        // Translate number in M-scale of notation to string representation, M - chars.length()
        // Gotten string will consist of position numbers of characters in chars set
        String valS = BigInteger.valueOf(val).toString(words.size()); // Ключевой вызов алгоритма

        // Cut beginning redundant characters (usually only 1)
        if (valS.length() > outLength) {
            valS = valS.substring(valS.length() - outLength);
        }

        Set<T> result = new HashSet();
        for (int i = 0; i < valS.length(); i++) {
            result.add(words.get(toPos(valS.charAt(i))));
        }
        return result;
    }

    private final char ZERO_CHAR = new Character('0').charValue();

    private int toPos(char c) {
        return c - ZERO_CHAR;
    }

    public static void main(String[] args) {
        List<String> array = new ArrayList<String>();
        array.add("A");
        array.add("B");
        array.add("C");
        array.add("D");

        Set<Set<String>> allPermutations = new Permutations().permutations(array);
        for (Set<String> perm : allPermutations) {
            System.out.println(perm);
        }
    }
}
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет