just backing something up

gistfile1.diff

Index: Modules/itertoolsmodule.c
===================================================================
--- Modules/itertoolsmodule.c	(revision 77795)
+++ Modules/itertoolsmodule.c	(working copy)
@@ -2312,7 +2312,6 @@
 	PyObject_GC_Del,		/* tp_free */
 };
 
-
 /* permutations object ************************************************************
   
 def permutations(iterable, r=None):
@@ -2342,7 +2341,6 @@
 	PyObject_HEAD
 	PyObject *pool;			/* input converted to a tuple */
 	Py_ssize_t *indices;            /* one index per element in the pool */
-	Py_ssize_t *cycles;		/* one rollover counter per element in the result */
 	PyObject *result;               /* most recently returned result tuple */
 	Py_ssize_t r;			/* size of result tuple */
 	int stopped;			/* set to 1 when the permutations iterator is exhausted */
@@ -2360,7 +2358,6 @@
 	PyObject *pool = NULL;
 	PyObject *iterable = NULL;
 	Py_ssize_t *indices = NULL;
-	Py_ssize_t *cycles = NULL;
 	Py_ssize_t i;
 	static char *kwargs[] = {"iterable", "r", NULL};
  
@@ -2389,16 +2386,13 @@
 	}
 
 	indices = PyMem_Malloc(n * sizeof(Py_ssize_t));
-	cycles = PyMem_Malloc(r * sizeof(Py_ssize_t));
-	if (indices == NULL || cycles == NULL) {
+	if (indices == NULL) {
     		PyErr_NoMemory();
 		goto error;
 	}
 
 	for (i=0 ; i<n ; i++)
 		indices[i] = i;
-	for (i=0 ; i<r ; i++)
-		cycles[i] = n - i;
 
 	/* create permutationsobject structure */
 	po = (permutationsobject *)type->tp_alloc(type, 0);
@@ -2407,7 +2401,6 @@
 
 	po->pool = pool;
 	po->indices = indices;
-	po->cycles = cycles;
 	po->result = NULL;
 	po->r = r;
 	po->stopped = r > n ? 1 : 0;
@@ -2417,8 +2410,6 @@
 error:
 	if (indices != NULL)
 		PyMem_Free(indices);
-	if (cycles != NULL)
-		PyMem_Free(cycles);
 	Py_XDECREF(pool);
 	return NULL;
 }
@@ -2430,7 +2421,6 @@
 	Py_XDECREF(po->pool);
 	Py_XDECREF(po->result);
 	PyMem_Free(po->indices);
-	PyMem_Free(po->cycles);
 	Py_TYPE(po)->tp_free(po);
 }
 
@@ -2449,11 +2439,11 @@
 	PyObject *oldelem;
 	PyObject *pool = po->pool;
 	Py_ssize_t *indices = po->indices;
-	Py_ssize_t *cycles = po->cycles;
 	PyObject *result = po->result;
 	Py_ssize_t n = PyTuple_GET_SIZE(pool);
 	Py_ssize_t r = po->r;
-	Py_ssize_t i, j, k, index;
+	Py_ssize_t i, j, k, l, index;
+	/* TODO make sure when we're done that I still need i */
 
 	if (po->stopped)
 		return NULL;
@@ -2471,7 +2461,7 @@
     			PyTuple_SET_ITEM(result, i, elem);
 		}
 	} else {
-		if (n == 0)
+		if (n < 2)
 			goto empty;
 
 		/* Copy the previous result tuple or re-use it if available */
@@ -2491,39 +2481,41 @@
 		/* Now, we've got the only copy so we can update it in-place */
 		assert(r == 0 || Py_REFCNT(result) == 1);
 
-                /* Decrement rightmost cycle, moving leftward upon zero rollover */
-		for (i=r-1 ; i>=0 ; i--) {
-			cycles[i] -= 1;
-			if (cycles[i] == 0) {
-				/* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
-				index = indices[i];
-				for (j=i ; j<n-1 ; j++)
-					indices[j] = indices[j+1];
-				indices[n-1] = index;
-				cycles[i] = n - i;
-			} else {
-				j = cycles[i];
-				index = indices[i];
-				indices[i] = indices[n-j];
-				indices[n-j] = index;
-
-				for (k=i; k<r ; k++) {
-					/* start with i, the leftmost element that changed */
-					/* yield tuple(pool[k] for k in indices[:r]) */
-					index = indices[k];
-					elem = PyTuple_GET_ITEM(pool, index);
-    					Py_INCREF(elem);
-					oldelem = PyTuple_GET_ITEM(result, k);
-    					PyTuple_SET_ITEM(result, k, elem);
-					Py_DECREF(oldelem);
+		do {
+			for (j=n-2 ; indices[j] >= indices[j+1] ; j--) {
+				if (j == 0) {
+					goto empty;
 				}
-				break;
 			}
+		
+			for (l=n-1 ; indices[j] >= indices[l] ; l--);
+
+			index = indices[j];
+			indices[j] = indices[l];
+			indices[l] = index;
+			k = j + 1;
+			l = n - 1;
+
+			while (k < l) {
+				index = indices[k];
+				indices[k] = indices[l];
+				indices[l] = index;
+				k++;
+				l--;
+			}
+
+		/* need this to skip permutations that don't matter.
+		 * i.e. if r=2 and iterable is ['a','b','c','d'],
+		 * then indices of [0,1,2,3] and [0,1,3,2] are equivalent. */
+		} while (j >= r);
+
+		for (i=j; i<r; i++) {
+			elem = PyTuple_GET_ITEM(pool, indices[i]);
+			Py_INCREF(elem);
+			oldelem = PyTuple_GET_ITEM(result, i);
+			PyTuple_SET_ITEM(result, i, elem);
+			Py_DECREF(oldelem);
 		}
-		/* If i is negative, then the cycles have all
-                   rolled-over and we're done. */
-		if (i < 0)
-			goto empty;
 	}
 	Py_INCREF(result);
 	return result;