Java自定义排列迭代器：实现previous()与hasPrevious()方法遇阻

需求说明 #

• 实现继承Iterator的Permutation类，新增previous()和hasPrevious()方法
• 单参构造器：接收生成排列的字符序列，参数为null或空时抛出IllegalArgumentException
• 双参构造器：接收字符序列及起始排列长度（范围1到序列长度），迭代从对应长度的首个排列开始，参数非法时抛出IllegalArgumentException
• 必须使用常量级存储，禁止存储与排列数量等规模的集合

问题现状 #

已成功实现hasNext()和next()方法，但hasPrevious()和previous()逻辑错误。测试输入为KChdt、起始长度1时，调用previous()返回KC，而非预期的t。

相关代码 #

public Permutations(String sequence, int startingLength) throws IllegalArgumentException {
    if (sequence == null || sequence.isEmpty()) {
        throw new IllegalArgumentException("Sequence must not be null or empty.");
    }
    if (startingLength < 1 || startingLength > sequence.length()) {
        throw new IllegalArgumentException(
                "Starting length must be between 1 and the length of the sequence.");
    }
    this.input = sequence;
    this.minPermutationLength = startingLength;
    this.maxPermutationLength = sequence.length();
    this.currentLength = startingLength;
    this.indexes = new int[startingLength];
    for (int i = 0; i < startingLength; i++) {
        indexes[i] = i;
    }
    this.hasPrevious = startingLength > 1;
    this.hasNext = true;
    System.out.println("input: " + input);
    System.out.println("startingLength: " + startingLength);
}

@Override
public boolean hasNext() {
    return hasNext;
}

@Override
public String next() throws NoSuchElementException {
    if (!hasNext) {
        throw new NoSuchElementException("No more permutations available.");
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < currentLength; i++) {
        sb.append(input.charAt(indexes[i]));
    }
    advanceIndexes();
    return sb.toString();
}

@Override
public boolean hasPrevious() {
    return hasPrevious;
}

@Override
public String previous() throws NoSuchElementException {
    if (!hasPrevious) {
        throw new NoSuchElementException("No previous permutations available.");
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < currentLength; i++) {
        sb.append(input.charAt(indexes[i]));
    }
    regressIndexes();
    System.out.println("previous: " + sb);
    return sb.toString();
}

private void advanceIndexes() {
    int i = currentLength - 1;
    while (i >= 0 && indexes[i] == maxPermutationLength - currentLength + i) {
        i--;
    }
    if (i >= 0) {
        indexes[i]++;
        for (int j = i + 1; j < currentLength; j++) {
            indexes[j] = indexes[j - 1] + 1;
        }
    } else {
        if (currentLength < maxPermutationLength) {
            currentLength++;
            indexes = new int[currentLength];
            for (int j = 0; j < currentLength; j++) {
                indexes[j] = j;
            }
        } else {
            hasNext = false;
        }
        hasPrevious = (currentLength > minPermutationLength) || (indexes[0] > 0);
    }
}

private void regressIndexes() {
    if (currentLength == minPermutationLength && indexes[0] == 0) {
        hasPrevious = false;
        return;
    }

    int i = currentLength - 1;
    while (i >= 0 && indexes[i] == i) {
        i--;
    }

    if (i >= 0) {
        indexes[i]--;
        for (int j = i + 1; j < currentLength; j++) {
            indexes[j] = maxPermutationLength - currentLength + j;
        }
    } else {
        currentLength--;
        indexes = new int[currentLength];
        for (int j = 0; j < currentLength; j++) {
            indexes[j] = maxPermutationLength - currentLength + j;
        }
        hasPrevious = currentLength != minPermutationLength || indexes[0] > 0;
    }
}

问题分析与修复方案 #

核心问题 #

previous()方法的执行顺序错误：当前逻辑是先返回当前索引对应的排列，再调用regressIndexes()回退索引。这导致返回的是回退前的内容，而非预期的前序排列。

比如测试场景中，当迭代到长度2的首个排列KC时（索引[0,1]），调用previous()会先返回KC，再回退到长度1的最后一个排列t（索引[4]），与预期返回t不符。

修复步骤 #

1. 调整previous()方法的执行顺序：先调用regressIndexes()回退到前序排列的索引，再构建并返回对应的字符串：

@Override
public String previous() throws NoSuchElementException {
    if (!hasPrevious) {
        throw new NoSuchElementException("No previous permutations available.");
    }
    regressIndexes(); // 先回退索引
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < currentLength; i++) {
        sb.append(input.charAt(indexes[i]));
    }
    System.out.println("previous: " + sb);
    return sb.toString();
}

2. 验证regressIndexes()的循环条件：原循环条件while (i >= 0 && indexes[i] == i)是正确的，它用于判断当前长度的排列是否已经是首个排列，若是则需要回退到上一长度的最后一个排列。

3. 确认hasPrevious的更新逻辑：当前代码中advanceIndexes()和regressIndexes()内的hasPrevious更新逻辑是正确的，无需修改。

测试验证 #

修复后，输入KChdt、起始长度1，当迭代到长度2的首个排列后调用previous()，会先回退到长度1的最后一个排列t的索引[4]，再返回t，符合预期。

内容的提问来源于stack exchange，提问作者Kate Johnson