using System;
using System.Collections;
public class nextpermutation : ArrayList
{
public nextpermutation(object[] x) : base(x)
{
}
public bool next()
{
return next(new Iterator(this, 0), new Iterator(this, this.Count));
}
private class Iterator
{
int mIndex = 0;
ArrayList mList;
public Iterator(ArrayList list, int index)
{
mIndex = index;
mList = list;
}
public Iterator Clone()
{
return new Iterator(mList, mIndex);
}
public static Iterator operator--(Iterator x)
{
x.mIndex--;
return x;
}
public static bool operator==(Iterator x, Iterator y)
{
return x.mIndex == y.mIndex;
}
public static bool operator!=(Iterator x, Iterator y)
{
return x.mIndex != y.mIndex;
}
//crap!
public override bool Equals(object o)
{
return false;
}
public override int GetHashCode()
{
return 0;
}
//end crap!
public static Iterator operator++(Iterator x)
{
x.mIndex++;
return x;
}
// public static bool operator > (Iterator x, Iterator y)
// {
// return ((IComparable) x.mList[x.mIndex]).CompareTo(y.mList[y.mIndex]) > 0;
// }
// public static bool operator < (Iterator x, Iterator y)
// {
// return ((IComparable) x.mList[x.mIndex]).CompareTo(y.mList[y.mIndex]) < 0;
// }
public object data
{
get
{
return mList[mIndex];
}
}
public void swap(Iterator right)
{
object tmp = mList[mIndex];
mList[mIndex] = right.data;
right.mList[right.mIndex] = tmp;
}
}
private void reverse(Iterator _First, Iterator _Last)
{ // reverse elements in [_First, _Last)
for (; _First != _Last && _First != --_Last; ++_First)
_First.swap(_Last);
}
private bool next(Iterator _First, Iterator _Last)
{ // permute and test for pure ascending, using operator<
Iterator _Next = _Last.Clone();
if (_First == _Last || _First == --_Next)
return (false);
for (; ; )
{
//find rightmost element smaller than successor
Iterator _Next1 = _Next.Clone();
//swap with rightmost element that's smaller, flip suffix
--_Next;
if (((IComparable)_Next.data).CompareTo(_Next1.data) < 0)
{
Iterator _Mid = _Last.Clone();
for (; !(((IComparable)_Next.data).CompareTo((--_Mid).data) < 0); )
;
_Next.swap(_Mid);
reverse(_Next1, _Last);
return (true);
}
if (_Next == _First)
{ // pure descending, flip all
reverse(_First, _Last);
return (false);
}
}
//return false;
}
}
|
using System;
using System.IO;
using System.Collections;
using ut;
public class testnextpermutation
{
string toString(nextpermutation list)
{
string s = "";
foreach (int i in list)
{
s += i + " ";
}
return s;
}
public void test1()
{
nextpermutation list = new nextpermutation(new object[] {1, 2, 3});
utx.assert(toString(list), "1 2 3 ");
utx.assert(list.next());
utx.assert(toString(list), "1 3 2 ");
utx.assert(list.next());
utx.assert(toString(list), "2 1 3 ");
utx.assert(list.next());
utx.assert(toString(list), "2 3 1 ");
utx.assert(list.next());
utx.assert(toString(list), "3 1 2 ");
utx.assert(list.next());
utx.assert(toString(list), "3 2 1 ");
utx.assertnot(list.next());
}
public void test2()
{
nextpermutation list = new nextpermutation(new object[] {1, 3, 2});
utx.assert(toString(list), "1 3 2 ");
utx.assert(list.next());
utx.assert(toString(list), "2 1 3 ");
utx.assert(list.next());
utx.assert(toString(list), "2 3 1 ");
utx.assert(list.next());
utx.assert(toString(list), "3 1 2 ");
utx.assert(list.next());
utx.assert(toString(list), "3 2 1 ");
//note: this is the way the original STL code works. see nextpermutation.cpp
utx.assertnot(list.next());
utx.assert(toString(list), "1 2 3 ");
utx.assert(list.next());
}
}
|