001/*
002 * Java Genetic Algorithm Library (jenetics-7.1.0).
003 * Copyright (c) 2007-2022 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
019 */
020package io.jenetics;
021
022import static java.lang.String.format;
023import static io.jenetics.internal.util.Arrays.shuffle;
024import static io.jenetics.internal.util.Bits.getAndSet;
025import static io.jenetics.internal.util.SerialIO.readInt;
026import static io.jenetics.internal.util.SerialIO.writeInt;
027
028import java.io.IOException;
029import java.io.InvalidObjectException;
030import java.io.ObjectInput;
031import java.io.ObjectInputStream;
032import java.io.ObjectOutput;
033import java.io.Serial;
034import java.io.Serializable;
035import java.util.stream.Collectors;
036import java.util.stream.IntStream;
037
038import io.jenetics.internal.math.Subset;
039import io.jenetics.internal.util.Bits;
040import io.jenetics.internal.util.Requires;
041import io.jenetics.util.ISeq;
042import io.jenetics.util.IntRange;
043import io.jenetics.util.MSeq;
044import io.jenetics.util.RandomRegistry;
045
046/**
047 * This chromosome can be used to model permutations of a given (sub) set of
048 * alleles.
049 *
050 * <pre>{@code
051 * final ISeq<String> alleles = ISeq.of("one", "two", "three", "four", "five");
052 *
053 * // Create a new randomly permuted chromosome from the given alleles.
054 * final PermutationChromosome<String> ch1 = PermutationChromosome.of(alleles);
055 * System.out.println(ch1);
056 * System.out.println(ch1.newInstance());
057 *
058 * // Create a new randomly permuted chromosome from a subset of the given alleles.
059 * final PermutationChromosome<String> ch2 = PermutationChromosome.of(alleles, 3);
060 * System.out.println(ch2);
061 * System.out.println(ch2.newInstance());
062 *
063 * // Console output:
064 * // > three|two|one|five|four
065 * // > two|one|four|five|three
066 * // > three|one|five
067 * // > five|three|one
068 * }</pre>
069 *
070 * Usable {@link Alterer} for this chromosome:
071 * <ul>
072 *     <li>{@link PartiallyMatchedCrossover}</li>
073 *     <li>{@link SwapMutator}</li>
074 * </ul>
075 * <p>
076 * <em><b>Implementation note 1:</b>
077 * The factory methods of the {@link AbstractChromosome} has been overridden so
078 * that no invalid permutation will be created.
079 * </em>
080 *
081 * <p>
082 * <em><b>Implementation note 2:</b>
083 * This class uses an algorithm for choosing subsets which is based on a
084 * FORTRAN77 version, originally implemented by Albert Nijenhuis, Herbert Wilf.
085 * The actual Java implementation is based on the  C++ version by John Burkardt.
086 * </em>
087 * <br>
088 * <em><a href="https://people.sc.fsu.edu/~burkardt/c_src/subset/subset.html">
089 *  Reference:</a></em>
090 *   Albert Nijenhuis, Herbert Wilf,
091 *   Combinatorial Algorithms for Computers and Calculators,
092 *   Second Edition,
093 *   Academic Press, 1978,
094 *   ISBN: 0-12-519260-6,
095 *   LC: QA164.N54.
096 * </p>
097 *
098 *
099 * @see EnumGene
100 * @see PartiallyMatchedCrossover
101 * @see SwapMutator
102 *
103 * @implNote
104 * This class is immutable and thread-safe.
105 *
106 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
107 * @since 1.0
108 * @version 6.0
109 */
110public final class PermutationChromosome<T>
111        extends AbstractChromosome<EnumGene<T>>
112        implements Serializable
113{
114        @Serial
115        private static final long serialVersionUID = 2L;
116
117        private final ISeq<T> _validAlleles;
118
119        // Private primary constructor.
120        private PermutationChromosome(
121                final ISeq<EnumGene<T>> genes,
122                final Boolean valid
123        ) {
124                super(genes);
125
126                assert !genes.isEmpty();
127                _validAlleles = genes.get(0).validAlleles();
128                _valid = valid;
129        }
130
131        /**
132         * Create a new {@code PermutationChromosome} from the given {@code genes}.
133         * If the given {@code genes} sequence contains duplicate entries, the
134         * created {@code PermutationChromosome} will be invalid
135         * ({@code ch.isValid() == false}).
136         *
137         * @param genes the enum genes the new chromosome consists of
138         * @throws NullPointerException if the given {@code genes} are null
139         * @throws IllegalArgumentException if the given {@code genes} sequence is
140         *         empty
141         */
142        public PermutationChromosome(final ISeq<EnumGene<T>> genes) {
143                this(genes, null);
144        }
145
146        /**
147         * Return the sequence of valid alleles of this chromosome.
148         *
149         * @return the sequence of valid alleles of this chromosome
150         */
151        public ISeq<T> validAlleles() {
152                return _validAlleles;
153        }
154
155        /**
156         * Check if this chromosome represents still a valid permutation (or subset)
157         * of the given valid alleles.
158         */
159        @Override
160        public boolean isValid() {
161                if (_valid == null) {
162                        final byte[] check = Bits.newArray(_validAlleles.length());
163                        _valid = _genes.forAll(g -> !getAndSet(check, g.alleleIndex()));
164                }
165
166                return _valid;
167        }
168
169        /**
170         * Create a new, <em>random</em> chromosome.
171         */
172        @Override
173        public PermutationChromosome<T> newInstance() {
174                return of(_validAlleles, length());
175        }
176
177        @Override
178        public PermutationChromosome<T> newInstance(final ISeq<EnumGene<T>> genes) {
179                return new PermutationChromosome<>(genes);
180        }
181
182        @Override
183        public String toString() {
184                return _genes.stream()
185                        .map(g -> g.allele().toString())
186                        .collect(Collectors.joining("|"));
187        }
188
189        /**
190         * Create a new, random chromosome with the given valid alleles and the
191         * desired length.
192         * <p>
193         * The following example shows how to create a {@code PermutationChromosome}
194         * for encoding a sub-set problem (of a fixed {@code length}).
195         * <pre>{@code
196         * final ISeq<String> basicSet = ISeq.of("a", "b", "c", "d", "e", "f");
197         *
198         * // The chromosome has a length of 3 and will only contain values from the
199         * // given basic-set, with no duplicates.
200         * final PermutationChromosome<String> ch = PermutationChromosome.of(basicSet, 3);
201         * }</pre>
202         *
203         * @since 3.4
204         *
205         * @param <T> the allele type
206         * @param alleles the base-set of the valid alleles
207         * @param length the length of the created chromosomes
208         * @return a new chromosome with the given valid alleles and the desired
209         *         length
210         * @throws IllegalArgumentException if {@code alleles.size() < length},
211         *         {@code length <= 0} or {@code alleles.size()*length} will
212         *         cause an integer overflow.
213         * @throws NullPointerException if one of the arguments is {@code null}
214         */
215        public static <T> PermutationChromosome<T> of(
216                final ISeq<? extends T> alleles,
217                final int length
218        ) {
219                Requires.positive(length);
220                if (length > alleles.size()) {
221                        throw new IllegalArgumentException(format(
222                                "The sub-set size must be be greater then the base-set: %d > %d",
223                                length, alleles.size()
224                        ));
225                }
226
227                final var rnd = RandomRegistry.random();
228                final int[] subset = Subset.next(alleles.size(), length, rnd);
229                shuffle(subset, rnd);
230
231                final ISeq<EnumGene<T>> genes = IntStream.of(subset)
232                        .mapToObj(i -> EnumGene.<T>of(i, alleles))
233                        .collect(ISeq.toISeq());
234
235                return new PermutationChromosome<>(genes, true);
236        }
237
238        /**
239         * Create a new, random chromosome with the given valid alleles.
240         *
241         * @param <T> the gene type of the chromosome
242         * @param alleles the valid alleles used for this permutation arrays.
243         * @return a new chromosome with the given alleles
244         * @throws IllegalArgumentException if the given allele sequence is empty.
245         */
246        public static <T> PermutationChromosome<T>
247        of(final ISeq<? extends T> alleles) {
248                return of(alleles, alleles.size());
249        }
250
251        /**
252         * Create a new, random chromosome with the given valid alleles.
253         *
254         * @since 2.0
255         *
256         * @param <T> the gene type of the chromosome
257         * @param alleles the valid alleles used for this permutation arrays.
258         * @return a new chromosome with the given alleles
259         * @throws IllegalArgumentException if the given allele array is empty.
260         * @throws NullPointerException if one of the alleles is {@code null}
261         */
262        @SafeVarargs
263        public static <T> PermutationChromosome<T> of(final T... alleles) {
264                return of(ISeq.of(alleles));
265        }
266
267        /**
268         * Create a integer permutation chromosome with the given length.
269         *
270         * @param length the chromosome length.
271         * @return a integer permutation chromosome with the given length.
272         * @throws IllegalArgumentException if {@code length <= 0}.
273         */
274        public static PermutationChromosome<Integer> ofInteger(final int length) {
275                return ofInteger(0, Requires.positive(length));
276        }
277
278        /**
279         * Create an integer permutation chromosome with the given range.
280         *
281         * @since 2.0
282         *
283         * @param start the start of the integer range (inclusively) of the returned
284         *        chromosome.
285         * @param end the end of the integer range (exclusively) of the returned
286         *        chromosome.
287         * @return a integer permutation chromosome with the given integer range
288         *         values.
289         * @throws IllegalArgumentException if {@code start >= end} or
290         *         {@code start <= 0}
291         */
292        public static PermutationChromosome<Integer>
293        ofInteger(final int start, final int end) {
294                if (end <= start) {
295                        throw new IllegalArgumentException(format(
296                                "end <= start: %d <= %d", end, start
297                        ));
298                }
299
300                return ofInteger(IntRange.of(start, end), end - start);
301        }
302
303        /**
304         * Create an integer permutation chromosome with the given range and length
305         *
306         * @since 3.4
307         *
308         * @param range the value range
309         * @param length the chromosome length
310         * @return a new integer permutation chromosome
311         * @throws NullPointerException if the given {@code range} is {@code null}
312         * @throws IllegalArgumentException if
313         *         {@code range.getMax() - range.getMin() < length},
314         *         {@code length <= 0} or
315         *         {@code (range.getMax() - range.getMin())*length} will cause an
316         *         integer overflow.
317         */
318        public static PermutationChromosome<Integer>
319        ofInteger(final IntRange range, final int length) {
320                return of(
321                        range.stream().boxed().collect(ISeq.toISeq()),
322                        length
323                );
324        }
325
326        /* *************************************************************************
327         *  Java object serialization
328         * ************************************************************************/
329
330        @Serial
331        private Object writeReplace() {
332                return new SerialProxy(SerialProxy.PERMUTATION_CHROMOSOME, this);
333        }
334
335        @Serial
336        private void readObject(final ObjectInputStream stream)
337                throws InvalidObjectException
338        {
339                throw new InvalidObjectException("Serialization proxy required.");
340        }
341
342        void write(final ObjectOutput out) throws IOException {
343                out.writeObject(_validAlleles);
344                for (EnumGene<?> gene : _genes) {
345                        writeInt(gene.alleleIndex(), out);
346                }
347        }
348
349        @SuppressWarnings({"unchecked", "rawtypes"})
350        static PermutationChromosome read(final ObjectInput in)
351                throws IOException, ClassNotFoundException
352        {
353                final ISeq validAlleles = (ISeq)in.readObject();
354                final MSeq genes = MSeq.ofLength(validAlleles.length());
355                for (int i = 0, n = validAlleles.length(); i < n; ++i) {
356                        genes.set(i, new EnumGene(readInt(in), validAlleles));
357                }
358
359                return new PermutationChromosome(genes.toISeq());
360        }
361
362}