3 개의 파일에 총 줄 수를 포함하는 배열이 있습니다. 예 : [3,4,5]. 세 파일의 모든 줄 조합을 제공하는 체계적인 방법으로 해당 배열을 0으로 세는 일련의 숫자를 생성하고 싶습니다. 이 예제는 3 개 파일 / 길이 -3 배열을 사용하지만 알고리즘은 임의의 길이로 배열을 작동 할 수 있어야합니다.
위의 예에서 솔루션은 다음과 같습니다.
[3,4,5] (line 3 from file 1, line 4 from file 2, line 5 from file 3)
[3,4,4]
[3,4,3]
[3,4,2]
[3,4,1]
[3,4,0]
[3,3,5]
[3,3,4]
[3,3,3]
[3,3,2]
등등...
이것에 대한 알고리즘을 생성하려는 첫 번째 시도는 배열의 위치를 재귀 적으로 감소시키고 그 위치가 0에 도달하면 그 이전의 위치를 감소시킵니다. 그러나 마지막 두 위치보다 더 많이 감소를 유지할 수 없습니다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FilePositionGenerator {
public static void main(String[] args) {
int[] starterArray = {2, 2, 2};
int[] counters = starterArray.clone();
List<Integer> results = new ArrayList<Integer>();
FilePositionGenerator f = new FilePositionGenerator();
f.generateFilePositions(starterArray, counters, (starterArray.length - 1), results);
}//end main
void generateFilePositions(int[] originalArray, int[] modifiedArray, int counterPosition, List<Integer> results) {
if (modifiedArray[counterPosition] == 0 && counterPosition > 0) {
modifiedArray[counterPosition] = originalArray[counterPosition];
counterPosition = counterPosition - 1;
} else {
modifiedArray[counterPosition] = modifiedArray[counterPosition] - 1;
System.out.println(Arrays.toString(modifiedArray));
generateFilePositions(originalArray, modifiedArray, counterPosition, results);
}
}
}
가변 길이 배열을 처리하려면 알고리즘이 재귀 적이어야 함을 이해하지만 생각하는 데 어려움이 있습니다. 그래서 저는 다른 접근법을 시도하기로 결정했습니다.
알고리즘 생성을위한 두 번째 시도는 현재 카운트 다운 위치 [가장 오른쪽 위치]에 포인터를 유지하는 이중 포인터 방법과 가장 오른쪽 위치가 0에 도달하면 감소 할 다음 가장 오른쪽이 아닌 위치 (pivotPointer)에 대한 포인터를 사용합니다. . 이렇게 :
import java.util.Arrays;
class DualPointer {
public static void main(String[] args) {
int[] counters = {2, 2, 2}; // initialize the problem set
int[] original = {2, 2, 2}; // clone a copy to reset the problem array
int[] stopConditionArray = {0, 0, 0}; // initialize an object to show what the stopCondition should be
int pivotLocation = counters.length - 1; // pointer that starts at the right, and moves left
int counterLocation = counters.length - 1; // pointer that always points to the rightmost position
boolean stopCondition = false;
System.out.println(Arrays.toString(counters));
while (stopCondition == false) {
if (pivotLocation >= 0 && counterLocation >= 0 && counters[counterLocation] > 0) {
// decrement the rightmost position
counters[counterLocation] = counters[counterLocation] - 1;
System.out.println(Arrays.toString(counters));
} else if (pivotLocation >= 0 && counters[counterLocation] <= 0) {
// the rightmost position has reached zero, so check the pivotPointer
// and decrement if necessary, or move pointer to the left
if (counters[pivotLocation] == 0) {
counters[pivotLocation] = original[pivotLocation];
pivotLocation--;
}
counters[pivotLocation] = counters[pivotLocation] - 1;
counters[counterLocation] = original[counterLocation]; // reset the rightmost position
System.out.println(Arrays.toString(counters));
} else if (Arrays.equals(counters, stopConditionArray)) {
// check if we have reached the solution
stopCondition = true;
} else {
// emergency breakout of infinite loop
stopCondition = true;
}
}
}
}
실행하면 두 가지 명백한 문제를 볼 수 있습니다.
[2, 2, 2]
[2, 2, 1]
[2, 2, 0]
[2, 1, 2]
[2, 1, 1]
[2, 1, 0]
[2, 0, 2]
[2, 0, 1]
[2, 0, 0]
[1, 2, 2]
[1, 2, 1]
[1, 2, 0]
[0, 2, 2]
[0, 2, 1]
[0, 2, 0]
첫째, pivotPointer와 currentCountdown이 둘 이상의 배열 셀 떨어져있을 때 pivotPointer가 제대로 감소하지 않습니다. 두 번째로 라인에 arrayIndexOutOfBounds가있어 counters[pivotLocation] = counters[pivotLocation] - 1;고정되면 알고리즘이 모두 제대로 실행되지 않습니다.
어떤 도움을 주시면 감사하겠습니다.
다른 접근 방식을 제안하겠습니다.
재귀의 아이디어는 다른 재귀 호출을 할 필요가없는 사소한 경우에 도달 할 때까지 각 재귀 호출에서 문제의 크기를 줄이는 것입니다.
n 요소의 배열에 대해 재귀 메서드를 처음 호출 할 때 마지막 인덱스 (n-1)의 값 범위에 대해 루프를 반복하고 첫 번째 배열에 대한 모든 조합을 생성하는 재귀 호출을 수행 할 수 있습니다. n-1 요소, 출력을 결합합니다.
다음은 일부 Java / 부분 의사 코드입니다.
첫 번째 호출 :
List<int[]> output = generateCombinations(inputArray,inputArray.length);
재귀 적 방법 List<int[]> generateCombinations(int[] array, int length):
List<int[]> output = new ArrayList<int[]>();
if length == 0
// the end of the recursion
for (int i = array[length]; i>=0; i--)
output.add (i)
else
// the recursive step
List<int[]> partialOutput = generateCombinations(array, length - 1)
for (int i = array[length]; i>=0; i--)
for (int[] arr : partialOutput)
output.add(arr + i)
return output
재귀 메서드는 List<int[]>. 즉, "output.add (i)"에서 단일 요소가있는 int 배열을 만들어 목록에 추가해야합니다. 반면에 output.add(arr + i)arr.length + 1 요소의 배열을 만들고 여기에 복사해야합니다. arr의 요소 다음에 i.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다