Anonymous user
Find the missing permutation: Difference between revisions
→{{header|JavaScript}}
(Link to topically related task) |
|||
Line 426:
<lang J> ((i.!4) A. 'ABCD') -. data
DBAC</lang>
=={{header|Java}}==
'''optimized'''
<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;
import com.google.common.base.Joiner;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
public class FindMissingPermutation {
public static void main(String[] args) {
Utils<Character> u = new Utils<Character>();
Joiner joiner = Joiner.on("").skipNulls();
ArrayList<Character> c = Lists.newArrayList('A', 'B', 'C', 'D');
ImmutableSet<String> s = ImmutableSet.of("ABCD", "CABD", "ACDB",
"DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB",
"CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC",
"BDAC", "CBDA", "DBCA", "DCAB");
for (ArrayList<Character> cs : u.Permutations(c))
if (!s.contains(joiner.join(cs)))
System.out.println(joiner.join(cs));
}
}</lang>
Output: DBAC
=={{header|JavaScript}}==
| |||