## Class PermutationToBitVectorProblem

• All Implemented Interfaces:
`Splittable<Initializer<BitVector>>`, `Initializer<BitVector>`
Direct Known Subclasses:
`PermutationToBitVectorProblem.DoubleCost`, `PermutationToBitVectorProblem.IntegerCost`

```public class PermutationToBitVectorProblem
extends Object
implements Initializer<BitVector>```

This class implements a mapping between Permutation problems and BitVector problems, enabling using `BitVector` search operators to solve problems defined over the space of `Permutation` objects. It can also be used as an `Initializer` of BitVectors by search algorithms to ensure that the search is using BitVectors of the appropriate length to represent permutations of the desired length for the problem you are solving. In fact, to ensure that your search is using the correct bit length, you should use this as your Initializer.

The mapping uses a classic transformation from vector of bits to a permutation of the N integers from 0 to N-1 that works as follows. Consider a list of integers L initially containing the N integers in sorted order: L = [0, 1, 2, ..., N-1]. The list L is circular, such that any integer is an index into L. For example, if L is of length 5, indexes 0, 5, 10, etc all refer to the element in position 0. Likewise, indexes 1, 6, 11, etc all refer to the element in position 1, and so forth. The bit vector must be length: (N - 1) ceiling(lg N). Each contiguous group of ceiling(lg N) bits is treated as an index into L. There are N-1 such indexes available based on the bit vector length. Each such index is used to select an element from L, add it to the next available position of an initially empty permutation P, and remove it from L. After N-1 such operations, there will be one element left in L, which is then added to the end. The `toPermutation(BitVector)` method implements this transformation.

Here is an example. Consider a very small permutation length N = 6. For this length permutation, the bit vector must be (6 - 1) ceiling(lg 6) = 5 * 3 = 15 bits in length. Let's consider the transformation from the bit vector 111110001010100.

• L is initially L = [0, 1, 2, 3, 4, 5], and P is initially P = [].
• The first 3 bits, 111, is 7 in decimal, and 7 mod 6 = 1. L[1]=1, so we remove the 1 from L and add it to the end of P. This leads to L = [0, 2, 3, 4, 5], and P is P = [1].
• The next 3 bits, 110, is 6 in decimal, and 6 mod 5 = 1. L[1]=2, so we remove the 2 from L and add it to the end of P. This leads to L = [0, 3, 4, 5], and P is P = [1, 2].
• The next 3 bits, 001, is 1 in decimal, and 1 mod 4 = 1. L[1]=3, so we remove the 3 from L and add it to the end of P. This leads to L = [0, 4, 5], and P is P = [1, 2, 3].
• The next 3 bits, 010, is 2 in decimal, and 2 mod 3 = 2. L[2]=5, so we remove the 5 from L and add it to the end of P. This leads to L = [0, 4], and P is P = [1, 2, 3, 5].
• The last 3 bits, 100, is 4 in decimal, and 4 mod 2 = 0. L[0]=0, so we remove the 0 from L and add it to the end of P. This leads to L = [4], and P is P = [1, 2, 3, 5, 0].
• Reached the end of the bit vector, and there is only one element left in L, the 4, which we simply add to the end of P to arrive at P = [1, 2, 3, 5, 0, 4].

This class has two nested subclasses, `PermutationToBitVectorProblem.DoubleCost` and `PermutationToBitVectorProblem.IntegerCost`, that handle the transformations from Permutation optimization problems with costs of type double and int, respectively (i.e., classes `OptimizationProblem` and `IntegerCostOptimizationProblem`).

• ### Nested Class Summary

Nested Classes
Modifier and Type Class Description
`static class ` `PermutationToBitVectorProblem.DoubleCost`
This class implements a mapping between Permutation problems and BitVector problems, where cost values are of type double.
`static class ` `PermutationToBitVectorProblem.IntegerCost`
This class implements a mapping between Permutation problems and BitVector problems, where cost values are of type int.
• ### Constructor Summary

Constructors
Constructor Description
`PermutationToBitVectorProblem​(int permutationLength)`
Initializes the PermutationToBitVectorProblem mapping for a specific permutation length.
• ### Method Summary

All Methods
Modifier and Type Method Description
`BitVector` `createCandidateSolution()`
Creates one candidate solution to a problem.
`PermutationToBitVectorProblem` `split()`
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms.
`int` `supportedBitVectorLength()`
Computes the length of BitVectors supported by this instance.
`Permutation` `toPermutation​(BitVector bits)`
Converts a BitVector to a Permutation.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### PermutationToBitVectorProblem

`public PermutationToBitVectorProblem​(int permutationLength)`
Initializes the PermutationToBitVectorProblem mapping for a specific permutation length.
Parameters:
`permutationLength` - The length of the permutations under optimization, in number of elements. This is NOT the length of the BitVectors. For example, if the problem is the Traveling Salesperson, and if the instance has 100 cities, then you would pass 100 for this parameter.
Throws:
`IllegalArgumentException` - if permutationLength is less than 1.
• ### Method Detail

• #### createCandidateSolution

`public final BitVector createCandidateSolution()`
Description copied from interface: `Initializer`
Creates one candidate solution to a problem.
Specified by:
`createCandidateSolution` in interface `Initializer<BitVector>`
Returns:
a candidate solution to a problem instance.
• #### split

`public PermutationToBitVectorProblem split()`
Description copied from interface: `Splittable`
Generates a functionally identical copy of this object, for use in multithreaded implementations of search algorithms. The state of the object that is returned may or may not be identical to that of the original. Thus, this is a distinct concept from the functionality of the `Copyable` interface. Classes that implement this interface must ensure that the object returned performs the same functionality, and that it does not share any state data that would be either unsafe or inefficient for concurrent access by multiple threads. The split method is allowed to simply return the this reference, provided that it is both safe and efficient for multiple threads to share a single copy of the Splittable object. The intention is to provide a multithreaded search with the capability to provide spawned threads with their own distinct search operators. Such multithreaded algorithms can call the split method for each thread it spawns to generate a functionally identical copy of the operator, but with independent state.
Specified by:
`split` in interface `Splittable<Initializer<BitVector>>`
Returns:
A functionally identical copy of the object, or a reference to this if it is both safe and efficient for multiple threads to share a single instance of this Splittable object.
• #### toPermutation

`public final Permutation toPermutation​(BitVector bits)`
Converts a BitVector to a Permutation. Assumes that the length of the BitVector bits is supportedBitVectorLength(), and behavior is undefined otherwise.
Parameters:
`bits` - The BitVector
Returns:
A Permutation derived from the BitVector
• #### supportedBitVectorLength

`public final int supportedBitVectorLength()`
Computes the length of BitVectors supported by this instance.
Returns:
the length of BitVectors supported by this instance