Translating that regex into C is trivial: (1) Find rightmost occurence of substring '01' (we are done if there is none), (2) change '01' to '10', (3) reverse the string to the right of that.

Finding the indices of the '1's is also simple.

Simple yes, but not quick.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Ok, here is the index-based algorithm:

use strict;
use warnings;

sub first_idx {
    my( $N, $M ) = @_;
    return ( $N-$M .. $N-1 );
}

sub next_idx {
    my( $N, $M, @idx ) = @_;
    return () if $idx[ -1 ] == $M-1;
    my $i = $M-1;
    $i-- while $i>0 and $idx[$i]-$idx[$i-1]==1;
    return ( @idx[0..$i-1], $idx[ $i ]-1, 
         map { $idx[ $i ] + $N - $idx[ $M - $_+ $i ] } $i+1 .. $M-1);
}

my $N = 5;
my $M = 3;
my @indices = first_idx( $N, $M );
1 while print( "@indices\n"), @indices = next_idx( $N, $M, @indices );
[download]

A chance to brush off my C :)

// inc_c - http://perlmonks.org/?node_id=1128230

#include <stdlib.h>
#include <stdio.h>

#define M 5 // place
#define N 3 // number of elements wanted

static int place[N];

int
step(void)
  {
  for(int i = 0; i < N; i++)
    {
    if(i < N - 1 ? place[i] < place[i + 1] - 1 : place[i] < M - 1 )
      {
      place[i]++;
      for(int j = i - 1; j >= 0; j--) place[j] -= place[0];
      return 1;
      }
    }
  return 0;
  }

int
main(int argc, char **argv)
  {
  int i;
  int more = 1;

  for(i = 0; i < N; i++) place[i] = i;

  while(more)
    {
    for(i = 0; i < N; i++) printf(" %d", place[i]);
    putchar('\n');
    more = step();
    }

  exit(0);
  }
[download]

That works. But it's about 40% slower than the A::C version I nicked. 11 seconds instead of 8 for the 601 million 16 from 32:

[17:27:38.79] C:\test\humanGenome>junk 32 16
^C
[17:41:10.28] C:\test\humanGenome>junk 32 16
Iters:601080390

[17:41:17.49] C:\test\humanGenome>junk2 32 16
^C
[17:41:40.82] C:\test\humanGenome>junk2 32 16
Iters:601080390

[17:41:52.30] C:\test\humanGenome>
[download]

junk2 is your code adapted to count rather than print.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

I'm still brushing the rust off my C. :) This one is 50% faster with only slight tweaks. This tight loop is *highly* sensitive to almost any change. BTW, going from -o2 to -o4 doubles speed.

// inc_c - http://perlmonks.org/?node_id=1128230
// 8.52 secs. for 16/32 count=601080390 -o2
// 3.16 secs. for 16/32 count=601080390 -o4

#include <stdlib.h>
#include <stdio.h>

#define N 16 // number of elements wanted
#define M 32 // place

static int place[N+1];
static int count = 0;

int
step(void)
  {
  int *p = place;

  for(int i = 0; i < N; i++, p++ )
    {
    if(*p < p[1] - 1)
      {
      ++*p;
      while( --i >= 0 ) *--p -= place[0];
      return 1;
      }
    }
  return 0;
  }

int
main(int argc, char **argv)
  {
  int i;
  int more = 1;

  for(i = 0; i < N; i++) place[i] = i;
  place[N] = M;

  while( more )
    {
    //for(i = 0; i < N; i++) printf(" %d", place[i]);
    //putchar('\n');
    count++;
    more = step();
    }

  printf("%d\n", count);

  exit(0);
  }
[download]