UVA – 146 – ID Codes

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s="";
		while(!(s = in.next()).equals("#")){
			
			Permuter<Character> perm = new Permuter<Character>(toArray(s));
			
			Vector<Character> next = perm.next();
			System.out.println(next ==null ? "No Successor": toString(next) );
			

		}
	}
}

I have used my own Permuter Class

class Permuter<T extends Comparable<? super T>> implements Iterable<Vector<T>>, Iterator<Vector<T>> {

	private Vector<T> list;

	public Permuter(Iterable<T> a){
		list = new Vector<T>();
		for(T e : a)
			list.add(e);
	}
	public Permuter(T[] array) {
		list = new Vector<T>(Arrays.asList(array));
	}

	public Vector<T> next() {
		if(list.size()<2) return null;
		int pivot = getPivot();
		if (pivot == -1)  return null; // The Given List is the last permutation ~

		int bigger = getGreaterThanPivotFromEnd(pivot);
		swap(pivot, bigger);
		Collections.reverse(list.subList(pivot + 1, list.size()));

		return list;
	}

	private void swap(int pivot, int bigger) {
		T temp = list.get(pivot);
		list.set(pivot, list.get(bigger));
		list.set(bigger, temp);
	}

	private int getGreaterThanPivotFromEnd(int pivot) {
		assert list.size() > 1 && pivot > -2 : "Wrong";
		int i = list.size() - 1;
		while (i > 0 && list.get(pivot).compareTo(list.get(i)) > -1)
			i--;
		return i;
	}

	private int getPivot() {
		assert list.size() > 1;
		int i = list.size() - 1;
		while (--i >= 0 && list.get(i).compareTo(list.get(i + 1)) > -1);
		return i;
	}

	@Override
	public Iterator<Vector<T>> iterator() {
		return this;
	}

	@Override
	public boolean hasNext() {
		return getPivot() > -1;
	}

	@Override
	public void remove() {
		next();
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: