Find the missing permutation: Difference between revisions
Content added Content deleted
Line 429: | Line 429: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
'''optimized''' |
'''optimized''' |
||
Following needs: [[User:Margusmartsepp/Contributions/Java/Utils.java|Utils.java]] |
|||
<lang javascript>import java.util.ArrayList; |
|||
import java.util.Collections; |
|||
public class Utils<T extends Comparable<T>> { |
|||
private void swap(ArrayList<T> data, int i, int j) { |
|||
T t = data.get(i); |
|||
data.set(i, data.get(j)); |
|||
data.set(j, t); |
|||
} |
|||
public ArrayList<Integer> mRange(int from, int to) { |
|||
ArrayList<Integer> result = new ArrayList<Integer>(); |
|||
for (int i = from; i <= to; i++) |
|||
result.add(i); |
|||
return result; |
|||
} |
|||
public boolean nextPerm(ArrayList<T> data) { |
|||
// find the swaps |
|||
int c = -1, d = data.size(); |
|||
for (int i = d - 2; i >= 0; i--) |
|||
if (data.get(i).compareTo(data.get(i + 1)) < 0) { |
|||
c = i; |
|||
break; |
|||
} |
|||
if (c < 0) |
|||
return false; |
|||
int s = c + 1; |
|||
for (int j = c + 2; j < d; j++) |
|||
if (data.get(j).compareTo(data.get(s)) < 0 && // |
|||
data.get(j).compareTo(data.get(c)) > 0) |
|||
s = j; |
|||
// do the swaps |
|||
swap(data, c, s); |
|||
while (--d > ++c) |
|||
swap(data, c, d); |
|||
return true; |
|||
} |
|||
@SuppressWarnings("unchecked") |
|||
public ArrayList<ArrayList<T>> Permutations(ArrayList<T> d) { |
|||
ArrayList<ArrayList<T>> result = new ArrayList<ArrayList<T>>(); |
|||
Collections.sort(d); |
|||
do { |
|||
result.add((ArrayList<T>) d.clone()); |
|||
} while (this.nextPerm(d)); |
|||
return result; |
|||
} |
|||
}</lang> |
|||
And code: |
|||
<lang javascript>import java.util.ArrayList; |
<lang javascript>import java.util.ArrayList; |
||
Line 505: | Line 453: | ||
}</lang> |
}</lang> |
||
Output: DBAC |
Output: <pre>DBAC</pre> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |