Skip to main content

Permutations with Duplicates in C

Calculating permutations has some fairly nifty algorithms out there. I recently ran into a permutation problem for which I couldn't find an existing algorithm. I admit that I didn't look too hard though. Basically, I needed the permutations of the elements of a set of size N over K slots. However, the permutations should include duplicate elements from the set, as K > N is valid configuration. This corresponds to NK permutations. Most algorithms I found did not permit duplicate elements.

As an example of an application for such a permutation algorithm, imagine the set of all function signatures of arity K-1 over N types. This corresponds to K slots with N possible choices for each slot.

I devised a fairly simple implementation of such a permutation algorithm. Essentially, N forms the base of an arbitrary-precision integer of size K. In other words, we have an array of elements with a maximum of N which index our set. To permute, we simply increment the first element and propagate any overflow across the rest of the array. If the carry is 1 when we're done iterating over the whole array, then we're done generating permutations.

Calculating permutations has been reduced to counting! Here is the C code:
#include <stdio.h>

void print(const unsigned *slots, const unsigned K)
{
unsigned i;
for (i = 0; i < K; ++i) {
printf("%4d", slots[i] );
}
printf("\n");
}

unsigned incr(unsigned *slots, const unsigned K, const unsigned N) {
unsigned i, carry;
print(slots, K);
for (i=0, carry=1; i < K; ++i) {
unsigned b = slots[i] + carry;
carry = b/N;
slots[i] = b % N;
}
return !carry;
}

void count(const unsigned N, const unsigned K) {
unsigned i;
unsigned *slots = calloc(K, sizeof(unsigned));
while(incr(slots, K, N)) {
}
}

//output:
// 0 0 0
// 1 0 0
// 0 1 0
// 1 1 0
// 0 0 1
// 1 0 1
// 0 1 1
// 1 1 1
int main(int argc, char ** argv) {
count(2, 3);
getchar();
}

The only assumption is that N is less than UINT_MAX. Also, for some insane reason that I cannot fathom, I can't get the slots to print in reverse order. The trivial reversal of the print loop induces an access violation under Windows:
void print(const unsigned *slots, const unsigned K)
{
unsigned i;
for (i = K-1; i >= 0; --i) {
printf("%4d", slots[i] );
}
printf("\n");
}

The mind boggles.

[Edit: a commenter pointed out the problem, so the solution can be found in the comments.]

Comments

Unknown said…
Your reverse print function coredumps because i is unsigned, so your termination test in the for loop (i >= 0) never fails.
Sandro Magi said…
Damnit, you're right. I thought the 0 condition properly handled it, but of course it doesn't since 0 is a valid value, and overflow is ignored in C. I'm too used to working in languages with overflow checking I suppose. :-)

The correct loop is of course:

void print(const unsigned *slots, const unsigned K)
{
  unsigned i;
  for (i = K-1; i >= 0-1; --i) {
    printf("%4d", slots[i] );
  }
  printf("\n");
}
Unknown said…
Using the test (i >= 0-1) should not print anything because K >= 0-1 forall K if your using unsigned arithmetic. I would change to signed arithmetic, but if you want to stick with unsigned you can use i < 0-1. Not very intuitive if your reading it though....
Sandro Magi said…
> Using the test (i >= 0-1)
> should not print anything
> because K >= 0-1 forall K if
> your using unsigned arithmetic.

Not true, as --i wraps to UINT_MAX which is greater than all K. I was going to use UINT_MAX from limits.h, but (0-1) does the job too. This should work on all architectures with ring arithmetic on integers, which is pretty much all of them.
Unknown said…
Woops. You are right and I'm a bit dyslexic... :)
Sandro Magi said…
No problem, I appreciate the correction! :-)

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen