### Re: Minimally changing combinations

by Yary (Pilgrim)
 on Jun 28, 2017 at 16:15 UTC ( #1193782=note: print w/replies, xml ) Need Help??

in reply to Minimally changing combinations

Thanks haukex for your code that generates an iterator, and it's efficient. It keeps track of the direction (1 or -1) for each position in the array @o and runs without needing a stack. I renamed the variables to help me understand it better-
```sub mixedgray_iterator {
my @domains = @_;
my @sizes = map { scalar @\$_ } @domains;
die "all items must have at least two positions"
if grep {\$_<2} @sizes;
my @cur_indices = (0) x @domains;
my @pos_to_loop_next = 0 .. @domains;
my @dir = (1) x @domains;
my \$done;
return sub {
return undef if \$done;
my \$rv = [map {\$domains[\$_][\$cur_indices[\$_]]} 0..\$#domains];
if (\$pos_to_loop_next[0]==@domains) { \$done=1; return \$rv }
(my \$domain,\$pos_to_loop_next[0]) = (\$pos_to_loop_next[0], 0);
\$cur_indices[\$domain] += \$dir[\$domain];
if (\$cur_indices[\$domain]==0 || \$cur_indices[\$domain]==\$sizes[
+\$domain]-1) {
\$dir[\$domain] = -\$dir[\$domain];
\$pos_to_loop_next[\$domain] = \$pos_to_loop_next[\$domain+1];
\$pos_to_loop_next[\$domain+1] = \$domain+1;
}
return \$rv;
}
}

thanos1983's references include Algorithm::Loops, its NestedLoots could be wrangled into producing what I'm looking for.

Thanks Eily "Gray code" was the term I'd forgotten (and "Hamming Distance" too) and nice compact code there!

Turns out my post was an "XY" problem. Like the authors of some combination modules, I'm running tests with all combinations of options. In these tests, each time an option changes, there's expensive setup to run first. My thought was to take the Gray-code-like sequence, and then compare each iteration with the values from the previous to see which setup code to run.

Or in other words, I want a sequence of "change option K to value V". Working on it!

Replies are listed 'Best First'.
Re^2: Minimally changing combinations
by Yary (Pilgrim) on Jun 29, 2017 at 17:35 UTC
It was easy once I figured out that it's just like counting... hope to have time this weekend to make it more feature-ful and put it on CPAN!
```#!/usr/bin/env perl

use strict;
use warnings;

use Data::Dump;

sub single_change_iterator {
my @domains = @_;
my \$it = 0;
my @dir = (1) x @domains;
my @pos = (0) x @domains;

\$it = sub {
# Initializion. Next call, use the real iterator.
\$it = sub {
my \$cur_dom;
for (\$cur_dom = 0;
\$cur_dom < @domains or return; # No more changes!
++\$cur_dom) {

# Are we at end position of this domain?
my \$upward = \$dir[\$cur_dom]==1;
if (\$pos[\$cur_dom] == (\$upward ? \$#{\$domains[\$cur_dom]
+} : 0)) {
# flip domain's direction, let loop continue
\$dir[\$cur_dom] *= -1;
}
else {
# Move current domain to next position
\$pos[\$cur_dom] += \$dir[\$cur_dom];
last;
}
}
return [\$cur_dom, \$domains[\$cur_dom][\$pos[\$cur_dom]]];
};

# End first call by initializing all domains
return map [\$_, \$domains[\$_][0]], 0 .. \$#domains
};

return \\$it;
}

my \$combo_it = single_change_iterator(['X','Y'], [qw(a b c)], [44,55])
+;

my @changes;
dd @changes while @changes = &\$\$combo_it;

single_change_itertor - Help build Cartesian product, by changing one
+value at a time

use Data::Dump;

my \$it = single_change_itertor(['X','Y'], [qw(a b c)], [1,2]);
dd \$_ while \$_ = &\$\$it;

prints

([0, "X"], [1, "a"], [2, 44])
[0, "Y"]
[1, "b"]
[0, "X"]
[1, "c"]
[0, "Y"]
[2, 55]
[0, "X"]
[1, "b"]
[0, "Y"]
[1, "a"]
[0, "X"]

This finds a way to cycle through all possible combinations of the
given sets- their Cartesian Product- by changing a single element at a
time. Given a set of domains, returns a handle to an iterator showing
which position changes, and what to. Similar to a Gray code, which
cycles through a set of numbers while only changing one digit.

Each call returns a list of array references. The inner array
reference is a pair,

[ index of domain that has a change , new value ]

The first iteration returns a pair for each domain so as to initialize
all the domains. Each subsequent call returns a single pair.

Create A New User
Node Status?
node history
Node Type: note [id://1193782]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (4)
As of 2019-05-20 18:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Do you enjoy 3D movies?

Results (128 votes). Check out past polls.

Notices?