约瑟夫环保存每一步弹出的值

题目：

//每隔3个报数的移除原来的List
[1,2,3,4,5,6,7]-初始序列
[1,2,4,5,6,7] => 3被算出并进入结果[3]
[1,2,4,5,7] => 6被算出并进入结果[3,6]
[1,4,5,7] => 2被算出并进入结果[3,6,2]
[1,4,5] => 7被算出并进入结果[3,6,2,7]
[1,4] => 5被算出并进入结果[3,6,2,7,5]
[4] => 1被算出并进入结果[3,6,2,7,5,1]
[] => 4被算出并进入结果[3,6,2,7,5,1,4]

法一：将算出的值移除List，然后继续往后计算

public static void main(String[] args) {
    List<Object> items = new ArrayList<>();
    items.add(1);
    items.add(2);
    items.add(3);
    items.add(4);
    items.add(5);
    items.add(6);
    items.add(7);
    List<Object> objects = fun(items, 3);
    objects.forEach(System.out::println);
}

private static <T> List<T> fun(final List<T> items, final int k) {
    int current = 0;
   List<T> answer= new ArrayList<>();
    while (items.size() > 0) {
        current = (current-1+k)%items.size();
        answer.add(items.remove(current));
    }
    return answer;
}

法二：先计算出移除的下标值，然后直接取List中的值
计算下标值的方法来源于约瑟夫环问题递归解法的一点理解
此文章只介绍了计算最后出环的值，衍生一下就可以得出每一步出环的值
<-- 符号是可以通过公式推出值的意思
由文章可知公式是 ( 新环中的数字 + 最大报数值 )% 旧总人数
最大报数值：每隔N个报数的值

//由一般到特殊
7人环第7次出环的值 <--6人环第6次出环的值 <--5人环第5次出环的值 <--4人环第4次出环的值 <--3人环第3次出环的值 <--2人环第2次出环的值 <--1人环第1次出环的值 == 0
7人环第6次出环的值 <--6人环第5次出环的值 <--5人环第4次出环的值 <--4人环第3次出环的值 <--3人环第2次出环的值 <--2人环第=1次出环的值 == (3-1)%2
7人环第5次出环的值 <--6人环第4次出环的值 <--5人环第3次出环的值 <--4人环第2次出环的值 <--3人环第1次出环的值 == (3-1)%3
...
7人环第2次出环的值 <--6人环第1次出环的值 == (3-1)%6
7人环第1次出环的值 == (3-1)%7

这样，就只需要知道每个环第一次出环的值，就可以推算出7人环的出环的值了
而很简单可以推出，每个环第一次出环的值公式为 (最大报数值 - 1) % 总人数

public static void main(String[] args) {
    List<Object> items = new ArrayList<>();
    items.add(1);
    items.add(2);
    items.add(3);
    items.add(4);
    items.add(5);
    items.add(6);
    items.add(7);
    //保存下标值
    List<Integer> index = funTo(items.size(), 3);
    List<Object> result = new ArrayList<>(items.size());
    for (Integer integer : index) {
        result.add(items.get(integer));
    }
    result.forEach(System.out::println);
}
private static List<Integer> funTo(final int size, final int k) {
    int start;
    List<Integer> index = new ArrayList<>();
    for (int j = 1; j <= size; j++) {
        start = (k - 1) % (size - j + 1);
        for (int i = 1; i < j; i++) {
            start = (start + k) % (size - j + i + 1);
        }
        index.add(start);
    }
    return index;
}