Декартова сила (специальный декартовский продукт) - выбирайте элементы из массива в повторяемом стиле - PullRequest
Новая
       62

Декартова сила (специальный декартовский продукт) - выбирайте элементы из массива в повторяемом стиле

0 голосов
/ 24 октября 2018

Ввод :
Имеется входной массив (предположим, что нет повторяющихся элементов) длиной n.

Выход:
И хотел бы напечатать все возможные массивы одинаковой длины n состоит из элементов из входного массива, каждый входной элемент может быть использован несколько раз в выходном массиве.

Советы:

  • n является переменной среди нескольких входов.

Например

Массив ввода: [0, 1, 2]

Ожидаемый результат:

  • 000
  • 001
  • 002
  • 010
  • 011
  • 012
  • 020
  • 021

  • 022

  • 100

  • 101
  • 102
  • 110
  • 111
  • 112
  • 120
  • 121

  • 122

  • 200

  • 201
  • 202
  • 210
  • 211
  • 212
  • 220
  • 221
  • 222

Существует 3 * 3 * 3 = 27 комбинаций, или вообще n^n для массива с длиной n.

Вопросы

  • Как напечатать это длямаленький ввод n (<= 5), вероятно, в рекурсивном стиле? </li>
  • Как эффективно распечатать это для большого ввода n, без переполнения в стеке, возможно, с одним циклом?
    например, когдаn = 9, есть 387420489 выходов, программа должна быть в состоянии обрабатывать такие входы.
  • Как должна называться эта проблема?Это не типичная перестановка, поскольку элементы повторяемы.Модификация к названию приветствуется.

Ответы [ 2 ]

0 голосов
/ 25 октября 2018

Я написал реализацию Java, которая включает в себя несколько алгоритмов:

Код - реализация

CartesianPower.java : 

import java.util.Arrays;

/**
 * Cartesian power of n elements.
 * <h2>Refer:</h2>
 * <li><a href="https://stackoverflow.com/questions/52977819">Original question, with radix & iteration solution.</a>
 * <li><a href="https://stackoverflow.com/questions/53012861">Additional question, with recursion solution.</a>
 * 
 * <h2>Algorithms:</h2>
 * <li><b>Radix</b>: intuitive, but not very efficient,
 * <li><b>Iteration</b>: best choice, most efficient & scalable,
 * <li><b>Recursion</b>: elegant, but not very intuitive, and performance is bad (or even stack overflow) for large input size,
 * <li>
 * 
 * @author eric
 * @date Oct 25, 2018 4:53:34 PM
 */
public class CartesianPower {
    public static final int MIN_ARR_LEN = 2; // min length of input array ,
    public static final int MAX_ARR_LEN = 10; // max length of input array,

    public static final int ARR_PRINT_LEN_LIMIT = 6; // max array length, that is allowed to print detailed output items to console,

    /**
     * Print cartesian power of array elements, by converting between radix.
     * <p>
     * time complexity: O(n) for each output item, and O(n^(n+1)) overall.
     * 
     * @param arr
     *            an array with length between [Character.MIN_RADIX, Character.MAX_RADIX]
     * @return count of cartesian, or -1 if radix is out of range,
     */
    public static <T> long cartesianPowerViaRadix(T arr[]) {
        int len = arr.length; // length of array, also the radix,
        // check radix range,
        if (len < MIN_ARR_LEN || len > MAX_ARR_LEN) {
            System.out.printf("%d is out of range [%d, %d]\n", len, MIN_ARR_LEN, MAX_ARR_LEN);
            return -1;
        }

        long count = 0;
        long totalCount = (long) Math.pow(len, len);
        T tmpArr[] = Arrays.copyOf(arr, len);

        while (count < totalCount) {
            String baseStr = Long.toString(count, len);

            for (int i = 0; i < baseStr.length(); i++) {
                char c = baseStr.charAt(i);
                int r = Integer.parseInt(String.valueOf(c), len);
                tmpArr[i] = arr[r];
            }

            for (int i = baseStr.length(); i < len; i++) {
                tmpArr[i] = arr[0];
            }

            printArr(tmpArr);
            count++;
        }

        System.out.printf("input arr: %s, total count: %d\n", Arrays.toString(arr), count);
        return count;
    }

    /**
     * Print cartesian power of array elements, by a single iteration.
     * <p>
     * time complexity:
     * <li>When don't print to console
     * <p>
     * O(1) for each output item, and O(n^n) overall.
     * <li>When print to console
     * <p>
     * O(n) for each output item, and O(n^(n+1)) overall.
     * 
     * @param n
     *            array length, array is assumed as numbers start from 0 and increase by 1, e.g [0, 1, 2],
     *            <p>
     *            it should be within range [CartesianProduct.MIN_ARR_LEN, CartesianProduct.MAX_ARR_LEN]
     * @return count of cartesian, or -1 if array length is out of range,
     */
    public static long cartesianPowerViaIterationN(int n) {
        // check range of array length,
        if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
            System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
            return -1;
        }

        long startTime = System.currentTimeMillis();

        long count = 0;
        int tmpArr[] = new int[n];
        Arrays.fill(tmpArr, 0);

        // initial case,
        printArr(tmpArr); // all elements as 0,
        count++;

        int i = n - 1;
        while (i >= 0) {
            tmpArr[i]++;
            if (tmpArr[i] == n) {
                tmpArr[i] = 0;
                i--;
            } else {
                printArr(tmpArr);
                i = n - 1;
                count++;
            }
        }

        long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
        System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
        return count;
    }

    /**
     * Print cartesian power of array elements, by a single iteration.
     * <p>
     * time complexity:
     * <li>When don't print to console
     * <p>
     * O(1) for each output item, and O(n^n) overall.
     * <li>When print to console
     * <p>
     * O(n) for each output item, and O(n^(n+1)) overall.
     * 
     * @param arr
     *            input array, could be of any type without order requirement,
     *            <p>
     *            its length should be within range [CartesianProduct.MIN_ARR_LEN, CartesianProduct.MAX_ARR_LEN]
     * @return count of cartesian, or -1 if array length is out of range,
     * @return
     */
    public static <T> long cartesianPowerViaIteration(T arr[]) {
        int n = arr.length;
        // check range of array length,
        if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
            System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
            return -1;
        }

        long startTime = System.currentTimeMillis();

        long count = 0;
        T tmpArr[] = Arrays.copyOf(arr, n); // tmp array,
        int idxArr[] = new int[n]; // index mapping array,
        Arrays.fill(idxArr, 0); // all indices as 0,

        // initial case,
        printIndirectionArr(idxArr, arr, tmpArr);
        count++;

        int i = n - 1;
        while (i >= 0) {
            idxArr[i]++;
            if (idxArr[i] == n) {
                idxArr[i] = 0;
                i--;
            } else {
                printIndirectionArr(idxArr, arr, tmpArr);
                i = n - 1;
                count++;
            }
        }

        long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
        System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);
        return count;
    }

    /**
     * Print cartesian power of array elements, via recursion, with raw int[] input.
     * <p>
     * Time complexity: O(1) for each output item, and O(n^n) overall.
     * 
     * @param arr
     * @return count of cartesian, or -1 if radix is out of range,
     */
    public static <T> long cartesianPowerViaRecursion(int arr[]) {
        int n = arr.length;
        // check range of array length,
        if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
            System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
            return -1;
        }

        long startTime = System.currentTimeMillis();
        int tmpArr[] = Arrays.copyOf(arr, n);

        long count = cartesianPowerViaRecursion(arr, tmpArr, 0);

        long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
        System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);

        return count;
    }

    /**
     * Print cartesian power of array elements, via recursion, the inner function, with raw int[] input.
     * 
     * @param arr
     *            input array,
     * @param tmpArr
     *            tmp array,
     * @param t
     *            current index in tmp array,
     * @return count of cartesian,
     */
    private static <T> long cartesianPowerViaRecursion(int arr[], int tmpArr[], int t) {
        int n = arr.length;
        long count = 0;

        if (t == n) {
            printArr(tmpArr);
            count++;
        } else {
            for (int i = 0; i < n; i++) {
                tmpArr[t] = arr[i];
                count += cartesianPowerViaRecursion(arr, tmpArr, t + 1);
            }
        }

        return count;
    }

    /**
     * Print cartesian power of array elements, via recursion.
     * <p>
     * Time complexity: O(1) for each output item, and O(n^n) overall.
     * 
     * @param arr
     * @return count of cartesian, or -1 if radix is out of range,
     */
    public static <T> long cartesianPowerViaRecursion(T arr[]) {
        int n = arr.length;
        // check range of array length,
        if (n < MIN_ARR_LEN || n > MAX_ARR_LEN) {
            System.out.printf("input length [%d] is out of range [%d, %d]\n", n, MIN_ARR_LEN, MAX_ARR_LEN);
            return -1;
        }

        long startTime = System.currentTimeMillis();
        T tmpArr[] = Arrays.copyOf(arr, n);

        long count = cartesianPowerViaRecursion(arr, tmpArr, 0);

        long during = (System.currentTimeMillis() - startTime); // during in milliseconds,
        System.out.printf("input arr length: %d, total count: %d, during: %d ms\n", n, count, during);

        return count;
    }

    /**
     * Print cartesian power of array elements, via recursion, the inner function.
     * 
     * @param arr
     *            input array,
     * @param tmpArr
     *            tmp array,
     * @param t
     *            current index in tmp array,
     * @return count of cartesian,
     */
    private static <T> long cartesianPowerViaRecursion(T arr[], T tmpArr[], int t) {
        int n = arr.length;
        long count = 0;

        if (t == n) {
            printArr(tmpArr);
            count++;
        } else {
            for (int i = 0; i < n; i++) {
                tmpArr[t] = arr[i];
                count += cartesianPowerViaRecursion(arr, tmpArr, t + 1);
            }
        }

        return count;
    }

    /**
     * Print int array, only when length <= limit.
     * 
     * @param arr
     * @return boolean, indicate whether printed,
     */
    private static boolean printArr(int arr[]) {
        if (arr.length > ARR_PRINT_LEN_LIMIT) {
            return false;
        }

        System.out.println(Arrays.toString(arr));
        return true;
    }

    /**
     * Print array, only when length <= limit.
     * 
     * @param arr
     * @return boolean, indicate whether printed,
     */
    private static <T> boolean printArr(T[] arr) {
        if (arr.length > ARR_PRINT_LEN_LIMIT) {
            return false;
        }

        System.out.println(Arrays.toString(arr));
        return true;
    }

    /**
     * Print indirection array, only when length <= limit.
     * 
     * @param idxArr
     *            contain index mapping,
     * @param arr
     * @param tmpArr
     * @return boolean, indicate whether printed,
     */
    private static <T> boolean printIndirectionArr(int idxArr[], T[] arr, T[] tmpArr) {
        if (arr.length > ARR_PRINT_LEN_LIMIT) {
            return false;
        }

        fillArrFromIndex(idxArr, arr, tmpArr); // fill tmp array,

        System.out.println(Arrays.toString(tmpArr));
        return true;
    }

    /**
     * Fill tmp array with elements from array, according to index mapping.
     * 
     * @param idxArr
     *            contain index mapping,
     * @param arr
     * @param tmpArr
     */
    private static <T> void fillArrFromIndex(int idxArr[], T[] arr, T[] tmpArr) {
        for (int i = 0; i < idxArr.length; i++) {
            tmpArr[i] = arr[idxArr[i]];
        }
    }
}

Советы:

  • Диапазондлина массива равна [2, 10], чтобы избежать слишком долгого запуска.
  • Только если длина массива <= 6, будет выводиться подробный вывод, в противном случае выводится только сводка. </li>

Код - контрольный пример

(все контрольные примеры используют TestNG )

CartesianPowerRadixTest.java:
(контрольный пример - для алгоритма радиуса) 

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * CartesianPower radix - test.
 * 
 * @author eric
 * @date Oct 25, 2018 5:04:54 PM
 */
public class CartesianPowerRadixTest {
    @Test
    public void testOrderedNum() {
        Integer arr[] = new Integer[] { 0, 1, 2 }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(arr), 27);
    }

    @Test
    public void testRandomNum() {
        Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(arr2), 27);

    }

    @Test
    public void testChar() {
        Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(charArr), 27);
    }

    @Test
    public void testObject() {
        Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(objectArr), 27);
    }

    @Test
    public void testOutOfRange() {
        Object tooShortArr[] = new Object[] { 1 }; // len = 1,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(tooShortArr), -1);

        Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
                31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRadix(tooLongArr), -1);
    }
}

CartesianPowerIterationNTest.java:
(контрольный пример - для итерационного алгоритма - вводдлина п, обрay принимается как начало массива int с 0, увеличивается на 1) 

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * CartesianPower iteration N - test.
 * 
 * @author eric
 * @date Oct 26, 2018 1:44:01 PM
 */
public class CartesianPowerIterationNTest {
    @Test
    public void testSmall() {
        int len = 3;
        Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(len), 27);
    }

    @Test
    public void testLarge() {
        int len = 9;
        Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(len), 387420489);
    }

    @Test
    public void testOutOfRange() {
        int tooShortLen = CartesianPower.MIN_ARR_LEN - 1;
        Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(tooShortLen), -1);

        int tooLongLen = CartesianPower.MAX_ARR_LEN + 1;
        Assert.assertEquals(CartesianPower.cartesianPowerViaIterationN(tooLongLen), -1);
    }
}

CartesianPowerIterationArrTest.java:
(тестовый пример - для алгоритма итерации - вводмассив любого типа без требования заказа) 

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * CartesianPower iteration array - test.
 * 
 * @author eric
 * @date Oct 26, 2018 2:48:50 PM
 */
public class CartesianPowerIterationArrTest {
    @Test
    public void testOrderedNum() {
        Integer arr[] = new Integer[] { 0, 1, 2 }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr), 27);
    }

    @Test
    public void testRandomNum() {
        Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr2), 27);
    }

    @Test
    public void testChar() {
        Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(charArr), 27);
    }

    @Test
    public void testObject() {
        Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(objectArr), 27);
    }

    @Test
    public void testLarge() {
        Object arr[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null }; // len = 9,
        Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(arr), 387420489);

        // Object arr2[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null, new Object() }; // len = 10,
        // Assert.assertEquals(CartesianProduct.cartesianViaLoopArr(arr2), 10000000000L);
    }

    @Test
    public void testOutOfRange() {
        Object tooShortArr[] = new Object[] { 1 }; // len = 1,
        Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(tooShortArr), -1);

        Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
                31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
        Assert.assertEquals(CartesianPower.cartesianPowerViaIteration(tooLongArr), -1);
    }
}

CartesianPowerRecursiveRawTest.java:
(тестовый случай - для алгоритма рекурсии - входной массив имеет типint []) 

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * CartesianPower recursion array - raw int[] input - test.
 * 
 * @author eric
 * @date Oct 27, 2018 4:09:18 AM
 */
public class CartesianPowerRecursiveRawTest {
    @Test
    public void testOrderedNum() {
        int arr[] = new int[] { 0, 1, 2 }; // len = 3
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 27);
    }

    @Test
    public void testRandomNum() {
        int arr2[] = new int[] { 0, 2, 1 }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr2), 27);
    }

    @Test
    public void testLarge() {
        int arr[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; // len = 9,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 387420489);

        // int arr2[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // len = 10,
        // Assert.assertEquals(CartesianPower.cartesianViaRecursion(arr2), 10000000000L);
    }

    @Test
    public void testOutOfRange() {
        int tooShortArr[] = new int[] { 1 }; // len = 1,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooShortArr), -1);

        int tooLongArr[] = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32,
                33, 34, 35, 36, 37, 38, 39 }; // len = 40,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooLongArr), -1);
    }
}

CartesianPowerRecursiveTest.java:
(тестовый случай - для алгоритма рекурсии - входной массив имеет универсальный тип T [])

import org.testng.Assert;
import org.testng.annotations.Test;

/**
 * CartesianPower recursion array - test.
 * 
 * @author eric
 * @date Oct 26, 2018 11:45:27 PM
 */
public class CartesianPowerRecursiveTest {
    @Test
    public void testOrderedNum() {
        Integer arr[] = new Integer[] { 0, 1, 2 };
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 27);
    }

    @Test
    public void testRandomNum() {
        Integer arr2[] = new Integer[] { 0, 2, 1 }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr2), 27);
    }

    @Test
    public void testChar() {
        Character charArr[] = new Character[] { 'a', 'b', 'c' }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(charArr), 27);
    }

    @Test
    public void testObject() {
        Object objectArr[] = new Object[] { 0, 'g', true }; // len = 3,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(objectArr), 27);
    }

    @Test
    public void testLarge() {
        Object arr[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null }; // len = 9,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(arr), 387420489);

        // Object arr2[] = new Object[] { 1, 0, 2, 'c', 'a', 'b', true, false, null, new Object() }; // len = 10,
        // Assert.assertEquals(CartesianProduct.cartesianViaRecursion(arr2), 10000000000L);
    }

    @Test
    public void testOutOfRange() {
        Object tooShortArr[] = new Object[] { 1 }; // len = 1,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooShortArr), -1);

        Object tooLongArr[] = new Object[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
                31, 32, 33, 34, 35, 36, 37, 38, 39 }; // len = 40,
        Assert.assertEquals(CartesianPower.cartesianPowerViaRecursion(tooLongArr), -1);
    }
}
0 голосов
/ 25 октября 2018

Один цикл сложен.Рекурсивный может быть наиболее интуитивным подходом.Но вот итеративная версия с двумя циклами, использующая Python, но избегающая магической функциональности от itertools, так что это не все, что зависит от языка: 

a = [0]*n
while(True):
  for i in range(n):
    a[i] += 1
    if a[i] == n:
      a[i] = 0
    else:
      break
  else:
    break
  print("".join(map(str, reversed(a))))

Идея заключается в следующем: индексировать свои числа справа налево(таким образом, reversed вызов там).Увеличьте самую правую цифру.Пока вы достигнете предела n, сбросьте его на ноль, но увеличивайте цифру еще на одну влево.По сути, это добавление 1 с использованием длинного сложения с переносом.Выходите из внутренней петли, когда нет больше переноса.Выходите из внешнего цикла, когда вы явно не выходите из внутреннего цикла, т. Е. Когда у вас есть перенос для всех цифр.

Тестовый прогон при https://ideone.com/n0ScW8.

Собственно теперь, когда я смотрю наКод снова, я вижу способ использовать один цикл, и избежать конструкции Python for-else, которая не имеет очевидного аналога в некоторых других языках.Давайте на этот раз воспользуемся JavaScript для разнообразия. 

a = Array.from(Array(n), x=>0);
i = n - 1;
while (i >= 0) {
  a[i]++;
  if (a[i] == n) {
    a[i] = 0;
    i--;
  } else {
    console.log(a.join(""));
    i = n - 1;
  }
}

Обратите внимание, что в обеих версиях отсутствует первоначальное решение 000… 0, поэтому они являются коротким решением.Легко добавить это заранее.Также обратите внимание, что я неправильно прочитал вопрос, поэтому я предполагаю массив чисел от 0 до n-1, в то время как на самом деле вы просили произвольный ввод.Но простая косвенность превратит одно в другое, поэтому я оставлю это как упражнение.

...