This is not determanistic but fair, reliable and reasonably fast.

Basically, it shuffles the indices and reshuffles if the outcome violates the specifications, as many times as it takes to get the required outcome.

For small arrays, it can take several attempts--with 10 couples I've seen it take 6 attempts--but with arrays that size it still doesn't take long. For larger arrays--100 or more--it rarely takes more than 2 attempts, and the larger the array, the less likely that it will need a second attempt.

#! perl -slw
use strict;
use List::Util qw[ shuffle ];

our $N ||= 10;

my @people = map{ $_ . 'a', $_ . 'b' } 1 .. $N;

my $iters = 1; ## Just for testing
my @indices = shuffle 0 .. $#people;

++$iters, @indices = shuffle 0 .. $#people while grep{
    $indices[ $_ + 1] & 1                         ## If the upper item
+ is odd
        ? $indices[ $_ ] +1 == $indices[ $_ + 1 ] ## the lower shouldn
+'t be -1
        : $indices[ $_ ] == $indices[ $_ + 1 ] +1 ## vice versa
} 0 .. $#people/2;

@people = @people[ @indices ]; ## shuffle the real data

print "Took $iters iterations"; ## How many tries?

print "@people[ $_, $_+1 ]" for 0 .. $#people/2 if <STDIN>; ## Allows 
+^C
[download]