There's a function in the standard-library for this: itertools.permutations
.
import itertools
list(itertools.permutations([1, 2, 3]))
If for some reason you want to implement it yourself or are just curious to know how it works, here's one nice approach, taken from http://code.activestate.com/recipes/252178/:
def all_perms(elements):
if len(elements) <=1:
yield elements
else:
for perm in all_perms(elements[1:]):
for i in range(len(elements)):
# nb elements[0:1] works in both string and list contexts
yield perm[:i] + elements[0:1] + perm[i:]
A couple of alternative approaches are listed in the documentation of itertools.permutations
. Here's one:
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
And another, based on itertools.product
:
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
Yes, there is a "next permutation" algorithm, and it's quite simple too. The C++ standard template library (STL) even has a function called next_permutation
.
The algorithm actually finds the next permutation -- the lexicographically next one. The idea is this: suppose you are given a sequence, say "32541". What is the next permutation?
If you think about it, you'll see that it is "34125". And your thoughts were probably something this: In "32541",
- there is no way to keep the "32" fixed and find a later permutation in the "541" part, because that permutation is already the last one for 5,4, and 1 -- it is sorted in decreasing order.
- So you'll have to change the "2" to something bigger -- in fact, to the smallest number bigger than it in the "541" part, namely 4.
- Now, once you've decided that the permutation will start as "34", the rest of the numbers should be in increasing order, so the answer is "34125".
The algorithm is to implement precisely that line of reasoning:
- Find the longest "tail" that is ordered in decreasing order. (The "541" part.)
- Change the number just before the tail (the "2") to the smallest number bigger than it in the tail (the 4).
- Sort the tail in increasing order.
You can do (1.) efficiently by starting at the end and going backwards as long as the previous element is not smaller than the current element. You can do (2.) by just swapping the "4" with the '2", so you'll have "34521". Once you do this, you can avoid using a sorting algorithm for (3.), because the tail was, and is still (think about this), sorted in decreasing order, so it only needs to be reversed.
The C++ code does precisely this (look at the source in /usr/include/c++/4.0.0/bits/stl_algo.h
on your system, or see this article); it should be simple to translate it to your language: [Read "BidirectionalIterator" as "pointer", if you're unfamiliar with C++ iterators. The code returns false
if there is no next permutation, i.e. we are already in decreasing order.]
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first;
++i;
if (i == last) return false;
i = last;
--i;
for(;;) {
BidirectionalIterator ii = i--;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*--j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes O(n!) time for all permutations in total, so only O(1) -- constant time -- per permutation.
The good thing is that the algorithm works even when you have a sequence with repeated elements: with, say, "232254421", it would find the tail as "54421", swap the "2" and "4" (so "232454221"), reverse the rest, giving "232412245", which is the next permutation.
Best Answer
I have put together something with unity. It generates solids with a Quickhull algorithm which is pretty easily explained and found around the web.
This will generate Convex Hulls of the input points. So I randomly generate points inside of a tree-shape.
Then after the blob is generated I can then shift around the vertices adjusting the normals accordingly. Things to keep in mind is to get the object the "low poly" look you need make sure each triangle has it's own vertex and normal and all three on the triangle are the same.
This solution is solidly 1.0 and only allows for one tree chunk but its what i'm currently using and is up on the asset store for anyone interested. Low Poly Tree Generator