[This is part two in a series about iterators.]
Like the odometer of a car, the odometer we consider is basically a counter, with one generalization: each position could cycle through a different number of "digits" (each position starts at digit 0).
[Digits in quotes, because we could have one position go from, say, 0 to 999, each number is considered a digit, in base 1000.]
The general odometer works just like the one in the car.
Every time you need to increment the odometer, you increment the digit in the rightmost position (going back to 0 if you are at the largest possible digit for that position). If the increment results in that position cycling back to 0, you increment the position to the left of it. If that results in cycling back of that position to 0, you move one position left and so on.
Basically, simulating hand addition with carries.
When all the digits reach the maximum value, we cannot increment anymore. An odometer can easily be implemented as an iterator, to provide a has_next, next interface with next incrementing the counter by one.
Here is how an implementation might look like (C++):
[If you want to try solving the problem of implementing a has_next, next type of iterator for permutations using an odometer, please stop reading]
While the method discussed below is not optimal (unlike Heap's method, [in fact, not even asymptotically optimal]), and generates permutations in a "weird" order (unlike Narayana Pandita's method of generating in lexicographic order), it is an interesting application of odometers.
Say we want to provide an iterator to generate all the permutations of $1,2, \dots, n$, with a has_next, next interface.
The idea is to use a suitable odometer as a black-box, and map each odometer state to a permutation uniquely.
Since there are $n!$ permutations, an odometer that suggests itself:
The odometer has $n-1$ digits, $d_1, d_2, \dots, d_{n-1}$ with $d_1$ being the left-most.
The maximum possible digit achievable by $d_1$ is $n-1$, and so total $n$ digits for $d_1$, which are $\{0,1,2, \dots, n-1\}$.
Maximum digit for $d_2$ is $n-2$ and so on (max for $d_i$ being $n-i$).
This odometer can count upto $n\times(n-1)\times\dots\times 1 = n!$, exactly the number of permutations.
To generate a permutation given the odometer $[d_1, d_2, \dots, d_{n-1}]$, we can use the following method.
Start with $n$ empty circles in a row.
Write $1$ in the $(d_1+1)^{th}$ circle from the left.
Write $2$ in the $(d_2+1)^{th}$ empty circle from the left.
Write $3$ in the $(d_3+1)^{th}$ empty circle from the left.
and so on.
Once you have written $n-1$, there will be one empty circle left, where you write $n$, resulting in a permutation of $1,2,\dots, n$.
Notice that in the resulting permutation, the number of numbers greater than $i$, which appear to the left of $i$ is precisely $d_i$. In other words $[d_1, d_2, \dots, d_{n-1}]$ is the inversion table of the permutation, which tells you how many inversions a given number has.
It is not difficult to see that each odometer state generates a unique permutation.
If the odometer can be implemented as an iterator with has_next, next, so can the permutation generator.
There is an easy $O(n^2)$ time algorithm to map the odometer state to the permutation. Even $O(n\log n)$ is achievable.
The Cartesian product of sets $A_1, A_2, \dots, A_n$ is the set of tuples $(a_1, a_2, \dots, a_n)$ such that $a_i \in A_i$.
If the size of $A_i$ is $s_i$, then the number of such tuples is $s_1\times s_2\times \dots \times s_n$.
An odometer for this is $[d_1, d_2, \dots, d_n]$ where $d_i$ cycles through $s_i$ digits. Given an odometer state $[d_1, d_2, \dots, d_n]$, we pick the $(d_i+1)^{th}$ element from $A_i$ for the corresponding element of the resulting tuple.
The mapping can be done in $O(n)$ time, assuming the $k^{th}$ element of $A_i$ can be picked in $O(1)$ time.
If we want to generate all the subsets of $\{a_1, a_2, \dots, a_n\}$, we can represent each set as a bit-vector $[v_1, v_2, \dots, v_n]$, where $v_i = 1$ iff $a_i$ is in the set.
We can use the odometer $[d_1, d_2, \dots, d_n]$ with each $d_i$ cycling through exactly two digits.
We pick $v_i = d_i$.
This mapping can be done in $O(n)$ time.
The generalized odometer seems to be a useful tool for use in implementing has_next, next type of iterators for certain combinatorial objects.
Also, given a number $M$ we can directly construct (and vice-versa) the odometer corresponding to $M$ increments, without having to increment $M$ times.
This direct mapping allows us to compute the $M^{th}$ permutation, Cartesian product, or subset directly (without having to perform $M$ increments). This would be useful to parallelize the generation and processing of those objects.
Introduction
Like the odometer of a car, the odometer we consider is basically a counter, with one generalization: each position could cycle through a different number of "digits" (each position starts at digit 0).
[Digits in quotes, because we could have one position go from, say, 0 to 999, each number is considered a digit, in base 1000.]
The general odometer works just like the one in the car.
Every time you need to increment the odometer, you increment the digit in the rightmost position (going back to 0 if you are at the largest possible digit for that position). If the increment results in that position cycling back to 0, you increment the position to the left of it. If that results in cycling back of that position to 0, you move one position left and so on.
Basically, simulating hand addition with carries.
When all the digits reach the maximum value, we cannot increment anymore. An odometer can easily be implemented as an iterator, to provide a has_next, next interface with next incrementing the counter by one.
Here is how an implementation might look like (C++):
#include <vector>
// Represents a generalized odometer.
class Odometer {
public:
// 0 is the right most position.
Odometer(const std::vector<int>& max_digits) {
_max_digits = max_digits;
for (int i = 0; i < max_digits.size(); i++) {
_odometer.push_back(0);
}
_overflow = false;
}
bool has_next() const {
for (int i = 0; i < _odometer.size(); i++) {
if (_odometer[i] != 0 ) {
return true;
}
}
// All zeroes. If we overflowed,
// we are at the end.
return false || !_overflow;
}
// returns the current, but increments before
// returning.
std::vector<int> next() {
_overflow = true;
std::vector<int> current = _odometer;
for (int i = 0; i < _odometer.size(); i++) {
_odometer[i] = (_odometer[i] + 1) % _max_digits[i];
if (_odometer[i] != 0) {
break;
}
}
return current;
}
private:
bool _overflow;
std::vector<int> _odometer;
std::vector<int> _max_digits;
}; We will now discuss how we can do a iterator based generation of permutations using an odometer (and briefly, Cartesian products and power-set enumeration).
Generating Permutations
[If you want to try solving the problem of implementing a has_next, next type of iterator for permutations using an odometer, please stop reading]
While the method discussed below is not optimal (unlike Heap's method, [in fact, not even asymptotically optimal]), and generates permutations in a "weird" order (unlike Narayana Pandita's method of generating in lexicographic order), it is an interesting application of odometers.
Say we want to provide an iterator to generate all the permutations of $1,2, \dots, n$, with a has_next, next interface.
The idea is to use a suitable odometer as a black-box, and map each odometer state to a permutation uniquely.
Since there are $n!$ permutations, an odometer that suggests itself:
The odometer has $n-1$ digits, $d_1, d_2, \dots, d_{n-1}$ with $d_1$ being the left-most.
The maximum possible digit achievable by $d_1$ is $n-1$, and so total $n$ digits for $d_1$, which are $\{0,1,2, \dots, n-1\}$.
Maximum digit for $d_2$ is $n-2$ and so on (max for $d_i$ being $n-i$).
This odometer can count upto $n\times(n-1)\times\dots\times 1 = n!$, exactly the number of permutations.
To generate a permutation given the odometer $[d_1, d_2, \dots, d_{n-1}]$, we can use the following method.
Start with $n$ empty circles in a row.
Write $1$ in the $(d_1+1)^{th}$ circle from the left.
Write $2$ in the $(d_2+1)^{th}$ empty circle from the left.
Write $3$ in the $(d_3+1)^{th}$ empty circle from the left.
and so on.
Once you have written $n-1$, there will be one empty circle left, where you write $n$, resulting in a permutation of $1,2,\dots, n$.
Notice that in the resulting permutation, the number of numbers greater than $i$, which appear to the left of $i$ is precisely $d_i$. In other words $[d_1, d_2, \dots, d_{n-1}]$ is the inversion table of the permutation, which tells you how many inversions a given number has.
It is not difficult to see that each odometer state generates a unique permutation.
If the odometer can be implemented as an iterator with has_next, next, so can the permutation generator.
There is an easy $O(n^2)$ time algorithm to map the odometer state to the permutation. Even $O(n\log n)$ is achievable.
Generating Cartesian Products
The Cartesian product of sets $A_1, A_2, \dots, A_n$ is the set of tuples $(a_1, a_2, \dots, a_n)$ such that $a_i \in A_i$.
If the size of $A_i$ is $s_i$, then the number of such tuples is $s_1\times s_2\times \dots \times s_n$.
An odometer for this is $[d_1, d_2, \dots, d_n]$ where $d_i$ cycles through $s_i$ digits. Given an odometer state $[d_1, d_2, \dots, d_n]$, we pick the $(d_i+1)^{th}$ element from $A_i$ for the corresponding element of the resulting tuple.
The mapping can be done in $O(n)$ time, assuming the $k^{th}$ element of $A_i$ can be picked in $O(1)$ time.
Generating Subsets
If we want to generate all the subsets of $\{a_1, a_2, \dots, a_n\}$, we can represent each set as a bit-vector $[v_1, v_2, \dots, v_n]$, where $v_i = 1$ iff $a_i$ is in the set.
We can use the odometer $[d_1, d_2, \dots, d_n]$ with each $d_i$ cycling through exactly two digits.
We pick $v_i = d_i$.
This mapping can be done in $O(n)$ time.
Conclusion
The generalized odometer seems to be a useful tool for use in implementing has_next, next type of iterators for certain combinatorial objects.
Also, given a number $M$ we can directly construct (and vice-versa) the odometer corresponding to $M$ increments, without having to increment $M$ times.
This direct mapping allows us to compute the $M^{th}$ permutation, Cartesian product, or subset directly (without having to perform $M$ increments). This would be useful to parallelize the generation and processing of those objects.
No comments:
Post a Comment