如何使用排列在 Java 中使用自定义迭代器向后迭代

问：

我正在尝试创建一个扩展 Iterator 并添加两个方法的 Permutation 类：previous（） 和 hasPrevious（）。

• 它必须提供一个带有一个参数的构造函数：一个字符串，其中包含将从中生成排列的有序字符序列。无效的参数应引发 IllegalArgumentException。
• 它必须提供具有两个参数的构造函数：一个字符串，其中包含将从中生成排列的有序字符序列，以及第一个排列的起始长度。第一次排列的长度必须介于 1 和字符串长度（包括字符串）之间，并且迭代器应从给定长度的第一个可能的排列开始。例如，new Permuations（“abcd”， 3） 将开始迭代 “abc”，而 newPermutations（“abcd”， 2） 将开始迭代 “ab”。无效的参数应引发 IllegalArgumentException。
• 由于排列的数量随着序列的长度呈指数增长，因此您的实现应仅使用常量存储。换句话说，它不能存储任何将增长到包含与排列数量相同的元素数的集合。请注意，根据上述规范，序列可能从序列的中间开始（取决于起始长度），并且仍然能够遍历序列中的所有排列。

我已经成功地找到了一种从 Iterator 实现 hasNext（） 和 next（） 方法的方法，但我真的在为 hasPrevious（） 和 previous（） 而苦苦挣扎。当我通过返回序列中的前一个元素并向后移动光标位置来反转我在下一个方法中前进索引时正在做的事情。我已经在这里呆了几个小时，我无法弄清楚我哪里出了问题。我高度怀疑我把事情复杂化了，而且有一种更巧妙的方法来完成这项任务。任何帮助将不胜感激。

  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（） 未返回预期的正确值：t，但为：KC 输入：KChdt 起始长度：1 上一篇： KC