삭제로 가능한 모든 순열 생성

Question

문자열의 하나 이상의 큰 문자를 삭제하여 가능한 모든 순열을 생성해야하지만 작은 문자는 변경되지 않습니다.

예 입력 :

AalAADBdBBDkCeCCA 

는 이제 하나 개의 큰 문자를 제거

• 하여 가능한 모든 순열을 생성하는 데 필요한 1 N BIG의 제거를 조합 한 여러 번
• 0 ~ m 번 제거 된 문자 (n = 입력의 직접 문자 수, m = 문자 발생 수) (가) 두 번째 또는 세 번째 제거 A는 차이가 없습니다 (고정! 원래 내가 제 1 및 제 2 쓴) 경우

의 손길이 닿지 않은

떠나는 작은 문자가 나는, 즉, 고유의 순열에만 관심이 있습니다. 물론 첫 번째 또는 마지막 A가 제거되면 차이가 발생합니다. 순열에 대한

예 :이 도움이 경우 구아바를 사용하고

AalAADBdBBDkCeCCA // original input also counts as permutation 
AalAADBdBB kCeCCA // last D removed 
alAAD dBBDkCeCCA // first A and first B removed 
Aal D dBBDkCeC A // second and third A removed, first B and last C removed 

. 일반 자바 솔루션도 괜찮을 것이다.

이 순열 및 고유 순열의 총계를 제공하는 수학 공식에 대한 이름이 있으면 순열 알고리즘 결과를 확인할 수 있으므로 (적어도 순열의 정확한 양과 관련하여) .

이 예제는 축소 된 문제이므로 입력이 이미 병합 된 문자열 대신 문자 목록이나 미리 구문 분석 된 형식으로 사용 가능하다고 가정 할 수 있습니다.

감사합니다.

업데이트 :

은 내가 솔루션, 피드백 환영을 찾은 것 같아요. 아이디어 : 각 큰 문자의 색인 (위치)을 추출하십시오. 그것들을 세트에 넣고이 세트의 파워 세트 P를 만듭니다. 이것은 가능한 삭제의 모든 순열을 제공합니다 (예를 들어 1,2와 2,1의 중복을 포함하여 1 = 2 = 같은 큰 문자의 경우)

Answer 1

나는 당신의 업데이트와 비슷한 생각을 가지고 있습니다 만, 아무 것도 필터링하지 않기 때문에 광산.

문자열에 대문자로 된 모든 종류의 이진 테이블을 만들었으므로 (소문자는 무시하지 않으므로 무시할 수 있음).

아주 간단한 예제로 시작하여 진행하십시오. 이진 테이블에서 0은 문자를 그대로 두는 것을 의미하고 1은 문자를 제거하는 것을 의미합니다.

A의 문자열 (또는 1 개의 대문자 만있는 임의의 문자열).AAAAA) 2- 치환 둘 개 수도 aaaAaBbb) 4- 치환

ABC 대

AB 
00 
10 
01 
11 

8 순열

ABCD위한

ABC 
000 
100 
010 
110 
001 
101 
011 
111 

16 순열

ABCD 
0000 
1000 
0100 
1100 
0010 
1010 
0110 
1110 
0001 
1001 
0101 
1101 
0011 
1011 
0111 
1111 

와 AB위한

A 
0 
1 

(또는 문자열

표시됩니다. 2^2, 2^3, 2^4 2^numberOfUppercaseCharacters

중복 된 문제를 제거하지 않고 총 순열을 제공합니다. 캐릭터 위치에서 각 스위치를 끄고 출력 문자열을 한 세트에 저장하는 무차별 대입 방식을 잘못 구현할 수 있습니다. 집합에 있으므로 복제본이 추가되지 않습니다.

그래서 각 대문자 문자의 인덱스 개념적으로 위의 진 테이블 문자열의 인덱스 위치와 B의 C를 대체하는 생각에서

를 얻기 위해 구문 분석 하여 입력 문자열을.

그래서

문자열을 aaAbbBb 우리가 인덱스 2, 5 (0 인덱스)

A B 
_ _ 
0 0 
1 0 
0 1 
1 1 

이

2 5 
_ _ 
0 0 
1 0 
0 1 
1 1 

된다 그래서 우리는 2까지 진수의 표현을하는 경우^numOfUppercase를 호출하고 작동해야하는 관련 값을 제거합니다. 아래 샘플에는 문자열이 있고 대문자 색인 목록은 하드 코드되어 있습니다. 적어도 당신은 당신의 해결책을 시험하고 시험 할 무언가가 있습니다.

이 접근법의 상한선에 대해서는 알지 못합니다. 순열의 큰 2 진 표현으로 대문자의 긴 문자열로 넘어갈 수 있습니다. 그 여기의

샘플 :

import java.math.BigInteger; 
import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.Set; 


public class StringProcessing { 


public static void main(String[] args) { 
    // TODO Auto-generated method stub 
    StringProcessing sp = new StringProcessing(); 
    sp.setUpProcessing(); 

} 

public void setUpProcessing() { 
    String input = "aaABCDcs"; 

    //Populate with indexes of Uppercase letters (loop though each char and check if [A-Z]) 
    ArrayList<Integer> indexes = new ArrayList<Integer>(); 
    indexes.add(2); 
    indexes.add(3); 
    indexes.add(4); 
    indexes.add(5); 

    Set<String> permutationStore = new HashSet<String>(); 
    BigInteger permutations = BigInteger.valueOf(2).pow(indexes.size()); //2^numOfUppercaseChars 


    int maxSize = getMaxLength(permutations); //Need this for padding binary with 0 

    for (BigInteger index = BigInteger.ZERO; index.compareTo(permutations) < 0; index = index.add(BigInteger.ONE)) { 
     String binary = index.toString(2); 
     // System.out.println(permutations + " " + index + " " + binary + ", for string: " + input); //NumOf Permutations, currentPermutation, binaryRepresentation 

     int lastIndex = binary.length() -1; 
     StringBuilder currentString = new StringBuilder(input); 
     String permutationString = process(lastIndex, binary, currentString, indexes, maxSize); 
     permutationStore.add(permutationString); 
     System.out.println(permutations + " " + index + " " + binary + ", for string: " + input + ", Stored: " + permutationString); 
    } 

    System.out.println(""); 
    for(String s : permutationStore) { 
     System.out.println(s); 
    } 

} 

public int getMaxLength(BigInteger permutations) { 
    BigInteger zeroBased = permutations.subtract(BigInteger.ONE); 
    return zeroBased.toString(2).length(); 
} 

public String process(int lastIndex, String binary, StringBuilder currentString, ArrayList<Integer> indexes, int maxSize) { 
    int indexFound = binary.lastIndexOf('1', lastIndex); 

    if (indexFound == -1) { 
     return currentString.toString(); 
    } 
    int padding = maxSize - binary.length(); //Add leading "0's" to binary 

    int index = indexFound + padding; 
    int charPos = indexes.get(index); 

    currentString.deleteCharAt(charPos); 
    process(indexFound-1, binary, currentString, indexes, maxSize); 

    return currentString.toString(); 
} 

}