java - 数组中字符串的排列需要以相同的顺序排列，但不是

Question

使用递归来打印 ArrayList 中名称字符串的所有排列，需要它们按特定顺序排列，有些行是正确的，然后有些行在切换排列的第一个单词的末尾附近会混乱。例如索引明智，它需要是 3,1,2 然后是 3,2,1 但是它是相反的。

我的输出：

• 朱莉娅卢卡斯米娅
• 朱莉娅·米娅·卢卡斯
• 卢卡斯·朱莉娅·米娅
• 卢卡斯·米娅·朱莉娅
• 米娅·卢卡斯·朱莉娅
• 米娅·朱莉娅·卢卡斯

预期输出：

• 朱莉娅卢卡斯米娅
• 朱莉娅·米娅·卢卡斯
• 卢卡斯·朱莉娅·米娅
• 卢卡斯·米娅·朱莉娅
• 米娅·朱莉娅·卢卡斯
• 米娅·卢卡斯·朱莉娅（这一行需要交换上面的那一行）

   public static void allPermutations(ArrayList<String> permList, ArrayList<String> nameList, 
   int index) {
      
      if (index == nameList.size() - 1) {
         for (int i = 0; i < nameList.size(); i++) {
            permList.add(nameList.get(i));
         }
         for (String val: permList) {
            System.out.print(val + " ");
         }
         System.out.println();
         permList.clear();
         
      } 
      for (int i = index; i < nameList.size(); i++) {
         Collections.swap(nameList, index, i);
         allPermutations(permList, nameList, index + 1);
         Collections.swap(nameList, index, i);
      }
         
      }
      
   }

   public static void main(String[] args) {
      Scanner scnr = new Scanner(System.in);
      ArrayList<String> nameList = new ArrayList<String>();
      ArrayList<String> permList = new ArrayList<String>();

      nameList.add("Julia");
      nameList.add("Lucas");
      nameList.add("Mia ");
      
      
      allPermutations(permList, nameList, 0);
      
   }

标签： javarecursionpermutation

Answer 1

假设

1. 允许迭代代码

逻辑

1. 初始化字符串数组和对应的整数数组，保持原始元素的顺序
2. 迭代计算下一个排列

下一个排列

1. 以相反的顺序扫描给定的输入
2. 找到枢轴索引，其中value[pivot] < value[pivot + 1]
3. 枢轴右侧的所有条目均按降序排列
4. 对于给定的排列，下一个排列将是一个更大的值（如果从数字上考虑）
5. 例如：1234 -> 1243 -> 1324 -> 1342
6. 找到比枢轴元素大的元素（在右侧）
7. 交换这两个元素
8. 枢轴索引右侧的所有元素仍然按降序排列
9. pivot + 1从to反转元素end（按升序排列）
10. 这是下一个排列

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Permutation {

    // iteratively compute all permutaions
    private static void permute(String[] permutation, Integer[] order) {
        boolean hasMore;
        do {
            System.out.println(Arrays.deepToString(permutation));
            hasMore = next(permutation, order);
        } while (hasMore);
    }

    // given a permutation, find the next permutation based on the order
    private static boolean next(String[] permutation, Integer[] order) {
        int pivot = order.length - 2;
        // check from last and find the first left index greater than its next right index
        while (pivot >= 0 && order[pivot + 1] < order[pivot]) {
            pivot--;
        }

        // if reached beginning, then completed
        if (pivot < 0) {
            return false;
        }

        // find the index of least bigger element on the right
        int swap = pivot + 1;
        while (swap < order.length && order[pivot] < order[swap]) {
            swap++;
        }
        swap--;

        // swap pivot and its least bigger elemment
        swap(order, swap, pivot);
        swap(permutation, swap, pivot);

        // reverse the descending part after pivot and turn into ascending
        reverse(order, pivot + 1, order.length - 1);
        reverse(permutation, pivot + 1, permutation.length - 1);

        return true;
    }

    private static <T> void reverse(T[] a, int left, int right) {
        while (left < right) {
            swap(a, left++, right--);
        }
    }

    private static <T> void swap(T[] a, int i, int j) {
        T temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        List<String> nameList = new ArrayList<>();

        nameList.add("Julia");
        nameList.add("Lucas");
        nameList.add("Mia");

        String[] permutation = nameList.toArray(new String[nameList.size()]);
        Integer[] order = IntStream.range(0, nameList.size()).boxed()
            .collect(Collectors.toList()).toArray(new Integer[nameList.size()]);
        permute(permutation, order);
    }
}