Java code for generating permutations of a list using Heap’s algorithm.<\/p>\n
\r\n\/**\r\n * Uses Heap's algorithm to produce all permutations of a given list.\r\n * We use an iterator to avoid having to use too much memory.\r\n *\r\n * @author t.wood\r\n *\r\n * Copyright 2016 Tim Wood\r\n *\r\n * Permission is hereby granted, free of charge, to any person \r\n * obtaining a copy of this software and associated documentation \r\n * files (the \"Software\"), to deal in the Software without restriction,\r\n * including without limitation the rights to use, copy, modify, merge,\r\n * publish, distribute, sublicense, and\/or sell copies of the Software,\r\n * and to permit persons to whom the Software is furnished to do so, \r\n * subject to the following conditions:\r\n * \r\n * The above copyright notice and this permission notice shall be \r\n * included in all copies or substantial portions of the Software.\r\n * \r\n * THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND,\r\n * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES\r\n * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.\r\n * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY\r\n * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, \r\n * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE \r\n * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r\n * \r\n * @param The type of item being permuted\r\n * @param The type resulting from decorating the permutation\r\n *\/\r\npublic final class PermutationIterator implements Iterator {\r\n private final Function, R> defensiveDecorator;\r\n private final List a;\r\n private R pending;\r\n\r\n private final int[] skel;\r\n private int i;\r\n\r\n \/**\r\n * An iterator of permutations\r\n *\r\n * @param a the list to permute\r\n * @param decorator a decorator to apply to the permutation, a defensive copy\r\n * of the permutation is taken before it is passed to the decorator\r\n *\/\r\n public PermutationIterator(final List a, final Function,R> decorator) {\r\n defensiveDecorator = t -> decorator.apply(new ArrayList<>(t));\r\n pending = defensiveDecorator.apply(a);\r\n this.a = new ArrayList<>(a);\r\n skel = new int[a.size()];\r\n i = 0;\r\n }\r\n\r\n @Override public boolean hasNext() {\r\n return pending != null;\r\n }\r\n\r\n @Override public R next() {\r\n if(pending == null) {\r\n throw new IndexOutOfBoundsException();\r\n }\r\n final R result = pending;\r\n pending = permute();\r\n return result;\r\n }\r\n\r\n private R permute() {\r\n while(i < a.size()) {\r\n if (skel[i] < i) {\r\n if (even(i)) {\r\n swap(a, 0, i);\r\n } else {\r\n swap(a, skel[i], i);\r\n }\r\n skel[i] += 1;\r\n i = 0;\r\n return defensiveDecorator.apply(a);\r\n } else {\r\n skel[i] = 0;\r\n i += 1;\r\n }\r\n }\r\n return null;\r\n }\r\n\r\n private void swap(final List a, final int i0, final int i1) {\r\n final T t = a.get(i0);\r\n a.set(i0, a.get(i1));\r\n a.set(i1, t);\r\n }\r\n\r\n private boolean even(final int i) {\r\n return i % 2 == 0;\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Java code for generating permutations of a list using Heap’s algorithm. \/** * Uses Heap’s algorithm to produce all permutations of a given list. * We use an iterator to avoid having to use too much memory. * * @author … Continue reading