java - 전치 암호 열거 형

참고 : 다음 게시물을 삭제했기 때문에 이전에이 게시물을 삭제했습니다. post하지만 내 문제에 어떻게 적용해야할지 모르겠습니다.java - 전치 암호 열거 형

전치 암호 해독기에서 일하고 있습니다. 나는 이미 정적 컬럼 (1,2,3,4 순서대로 유지)의 문제를 해결했지만 길이에 대한 가능한 순열의 배열을 만드는 방법을 모르겠습니다. (매개 변수로 감안할 때) 가장 쉬운 방법은 일종의 재귀 적 방법이지만 시도하는 동안 나는 노력에서 길을 잃고있다.

1,2,3,4,5,6 
2,1,3,4,5,6 
2,3,1,4,5,6 
...

출처

2017-12-14 Dagarian

을, 내 친구 (아니 잠시 매우 혼란되고, 그리고 몇 가지 다른 일을 시도 후 :

는

예 배열이 포함됩니다 (하루 종일 코딩 꽤 피곤했습니다) n 항목의 n! 순열이 있다는 것을

가

public static void main(String[] args) { 
     Nibba nib = new Nibba(); 
     List<Character> characterSet = new ArrayList<>(); 
     characterSet.add('1'); 
     characterSet.add('2'); 
     characterSet.add('3'); 
     characterSet.add('4'); 
     characterSet.add('5'); 
     characterSet.add('6'); 

     List<String> perms = nib.generatePermutations(characterSet); 
     // filter only the permutations of length 6 
     perms = perms.stream().filter(p -> p.length() == characterSet 
       .size()).collect(Collectors.toList()); 
     for (String s : perms) { 
      System.out.println(s); 
     } 
     System.out.println("Total permutations = " + perms.size()); 
    } 

    private List<String> generatePermutations(List<Character> characterSet) { 
     List<String> permutations = new ArrayList<>(); 

     for (int idx = 0; idx < characterSet.size(); idx++) { 
      char character = characterSet.get(idx); 

      // Initialise first "permutation" 
      if (idx == 0) { 
       permutations.add(String.valueOf(character)); 
       continue; 
      } 

      ArrayList<String> oldPerms = new ArrayList<>(permutations); 
      for (String subPermutation : oldPerms) { 
       insertPermutations(permutations, subPermutation, character); 
      } 
     } 

     return permutations; 
    } 

    /** 
    * Insert permutations into the given list 
    * 
    * @param list the list 
    * @param str the string 
    * @param c the character to insert at each point in the string 
    */ 
    private void insertPermutations(List<String> list, String str, char c) { 
     for (int i = 0; i <= str.length(); i++) { 
      String newStr = str.substring(0, i) + c + str.substring(i); 
      list.add(newStr); 
     } 
    }

출처

2017-12-14 23:27:47 Dagarian

리콜 : 여기에 사용자가) 나에게 다음과 같은 자바 솔루션을했다. n! 쉽게 다음과 같은 방식으로 이해 될 수있다 :

1. There are `n` options for choosing the first item. 
2. There are `n-1` items remaining from which to choose the second item 
... 
n-1. There are `2` options left for the `n-1`-th item. 
n. There is only 1 item left for the `n`-th position.

따라서 항목을 주문하는 방법에 대한 (n) * (n-1) * (n-2) * ... (2) * (1) = n! 전체 선택이있다.

이것은 혼합 기수 번호 체계를 사용하여 순열을 열거하는 방법을 직접 보여줍니다. 이 구성표에서 최상위 자릿수는 n이며 그 다음 최상위 자릿수는 n-1 등입니다.

당신은 다음과 같은 방법으로 순열 선택 등의 혼합 기수 번호를 사용 : 배열에서 요소를 선택

를 사용하여 가장 중요한 자리를 (첫 번째 숫자는 [0, n-1] 범위 유의하고, n 중에서 선택할 요소가 있으므로 선택할 항목의 인덱스로 사용할 수 있습니다.
배열에서 선택한 요소를 제거하고 해당 요소가 치환 된 배열의 첫 번째 요소임을 기록한 다음 나머지 요소를 압축합니다 배열의 앞쪽으로
는 그것을 기록 선택된 요소를 제거
사용 나머지 항목에서 요소를 선택하는 두 번째 최상위 디지트 (이 숫자 값이 [0, n-2] 내지 유의하고 나머지 N-1 자리가있다) 순차 배열의 두 번째 요소
모든 항목이 선택 될 때까지 반복하십시오.

우리는 리틀 엔디안 자리 순서로 혼합 기수 번호를 나타내는 배열을 사용하는 경우, 우리는 할 것이다 다음 당신은 다음과 같은 방법이 혼합 기수의 수를 증가

int mixed_radix[n] = {0};

: 제로로 다시 돌아 랩 일단

//Increment the least-significant digit 
mixed_radix[0]++; 

//Ripple overflow toward the most-significant digit 
for(i=0; i<n; i++) { 
    if(mixed_radix[i] > i) { 
    mixed_radix[i] = 0; 
    if(i < n-1)mixed_radix[i+1]++; 
    } 
    else { 
    break; 
    } 
}

그래서 우리는 중지 0으로 혼합 기수 번호를 초기화하고 모든 가능한 가치를 통해 증가 할 수있는 방법이있다. (또는 n!-1 증분 이후 ...)

이 더 간단 할 수있는 사랑스러운 수치 트릭이있다, 말했다 모든 :

우리의 n! 순열이 있다는 것을 알고 다음과 같은 방법으로 정수에서 못생긴 혼합 기수 번호를 풀 수 n 품목;

int working = val; //val in the range [0, n!-1] 
for(j=0 j<n; j++) { 
    mixed_radix[j] = working % (j+1); 
    working /= (j+1); 
}

그래서 범위 0을 통해 val를 실행하는 외부 루프 내에서이 "풀기"루프를 삽입 : 다음은 정수 값과 혼합 기수 번호 사이에 전단 사 매핑을 제공 [0, n!-1] 범위의 정수 val에 대한 ~ n!-1은 가능한 기수를 열거하는 혼합 기수 (mixed-radix numbers)를 열거하는 훨씬 더 밀도가 높은 방법입니다. 또한 각 순열에 정수를 할당하여 효율적으로 이름을 지정합니다. :)

출처

2017-12-15 03:02:07 lockcmpxchg8b

java - 전치 암호 열거 형

답변

관련 문제