FilesExpand file tree

 master

/

Permutation.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (54 loc) · 1.31 KB

 master

/

Permutation.java

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (54 loc) · 1.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

/*

* Verified

* https://atcoder.jp/contests/abc054/submissions/16977824

*/

class Permutation implements java.util.Iterator<int[]>, Iterable<int[]> {

private int[] next;

public Permutation(int n) {

next = java.util.stream.IntStream.range(0, n).toArray();

}

@Override

public boolean hasNext() {

return next != null;

}

@Override

public int[] next() {

int[] r = next.clone();

next = nextPermutation(next);

return r;

}

@Override

public java.util.Iterator<int[]> iterator() {

return this;

}

public static int[] nextPermutation(int[] a) {

if (a == null || a.length < 2)

return null;

int p = 0;

for (int i = a.length - 2; i >= 0; i--) {

if (a[i] >= a[i + 1])

continue;

p = i;

break;

}

int q = 0;

for (int i = a.length - 1; i > p; i--) {

if (a[i] <= a[p])

continue;

q = i;

break;

}

if (p == 0 && q == 0)

return null;

int temp = a[p];

a[p] = a[q];

a[q] = temp;

int l = p, r = a.length;

while (++l < --r) {

temp = a[l];

a[l] = a[r];

a[r] = temp;

}

return a;

}

}