Как сделать цикл над циклами в Java? - PullRequest
Новая
       49

Как сделать цикл над циклами в Java?

2 голосов
/ 24 марта 2010

Я хотел бы сделать цикл над следующими элементами:

[1,2,11,12,21,22,111,112,121,122, ...., 222222]

или например

[1,2,3,11,12,13,21,22,23,31,32,33,111,112,113, ... 333333333]

Как я могу сделать это на Java? В моем конкретном случае я использую 4 цифры (1,2,3,4), а длина последнего номера может быть от 1 до 10.

Мне удалось сделать это на Python и PHP. В первом случае я использовал списки над списками. Я начал с [[1], [2],] затем для каждого элемента списка я добавил 1 и 2, поэтому я получил [[1,1], [1,2], [2,1], [2 , 2]] и т. Д .: 

nchips = sum(chips)
traj = [[]]
last = [[]]    
while len(last[0]) < nchips:
    newlast = []
    for tr in last:
        for d in [1,2,3,4]:
        newlast.append(tr + [d])
    last = newlast
    traj += last

Когда я делал это в PHP, я использовал число с базой 3. Но это было хитрое и не элегантное решение. 

    for ($i=-1; $i<=$n; $i+=1) {

    if ($i>-1) {
        $n5 = base_convert($i,10,5);
        $n5_str = strval($n5);
        $tr = array();
        $found = 0;
        for ($j=0; $j<strlen($n5_str); $j+=1) {
        $k = $n5_str[$j];
        if ($k==0) {
            $found = 1;
            break;
        }
        array_push($tr,$k);
        }
        if ($found==1)
        continue;
    } else {
        $tr = array();
    }
}

Легко ли это сделать на Java?

Ответы [ 4 ]

5 голосов
/ 24 марта 2010

Это выглядит очень похоже на подсчет с цифрами в заданной базе. (Основы 2 и 3 для ваших примеров) Вы можете легко преобразовать целое число в строку заданного основания, используя Integer.toString, и отобразить символы этой строки в символы. Пример: 

Integer.toString(6, 2) -> "011"

сопоставить эту строку с массивом символов, а затем сопоставить этот массив с вашими символами. В вашем случае это будет: «0» -> 1 и «1» -> 2.

Это не самое эффективное решение, но оно позволяет Integer.toString выполнять грязную работу, оставляя вам возможность выполнять простое преобразование массива.

Чтобы преобразовать наоборот, вы можете преобразовать массив в строку и затем использовать Integer.parseInt, чтобы снова извлечь представление int.

Если вам нужно выполнить арифметику (я полагаю, в основном ++ и - для предыдущего и следующего элемента цикла), делайте их на целое число и конвертируйте туда и обратно при необходимости.

Отказ от ответственности: я давно не кодировал в java, поэтому имена методов и классов могут быть отключены.

РЕДАКТИРОВАТЬ: вы всегда можете использовать big int, если вам нужно больше символов, чем может быть помещено в 32- и 64-разрядных целых числах.

Ответ на комментарий:

Как прокомментировали люди, у этого подхода есть проблемы с ведущими нулями. Очевидное решение заключается в добавлении некоторого значения N ^ (n + 1) к целочисленному представлению перед преобразованием в строку, где N - это основание, а n - это количество символов. Это приведет к преобразованию 1,1,2 в 1001 вместо 001, что позволит эффективно использовать нули.

Но этот недостаток заключается в том, что он становится слишком сложным решением, чтобы на самом деле быть простым решением, каким оно и было первоначально задумано.

2 голосов
/ 24 марта 2010 
public class Cycle {
    static void advance(StringBuilder sb, int B) {
        int pos = sb.length();
        while (--pos != -1 && sb.charAt(pos) == '0' + B) {
            sb.setCharAt(pos, '1');
        }
        if (pos == -1) {
            sb.insert(++pos, '0');
        }
        sb.setCharAt(pos, (char) (sb.charAt(pos) + 1));
    }

    public static void main(String args[]) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 20; i++) {
            advance(sb, 3);
            System.out.println(sb);
        }
    }
}

Продвижение осуществляется следующим образом:

  • Идите направо налево (--pos)
  • Ролловер все B с 1 с
  • Пока вы не найдете что-то меньшее, чем B или не ударитесь в стену (pos == -1)
  • Если вы попали в стену, вставьте 0
  • Увеличение символа на pos
1 голос
/ 24 марта 2010

Я полагаю, что ваша задача является комбинаторной задачей, и вы должны реализовать комбинаторный алгоритм для поиска уникальных комбинаций заданных чисел (1,2,3,4) - и повторить этот алгоритм от 1 до желаемой длины.

И я не могу представить, какие специфические особенности Java вы можете использовать здесь. Это будет несколько итераторов.

Для обсуждения алгоритмов советую прочитать Алгоритм возврата всех комбинаций k элементов из n

1 голос
/ 24 марта 2010

Если вас не интересует порядок генерации (я имею в виду, что он сначала произведет 1; 11; 111, а затем 1; 2; 3), используйте это: 

public static void gen(int level) {
    if (level > 0) {
        for (int i = 0; i < level; i++)
            System.out.print(arr[i] + " ");     
        System.out.println();
    }

    if (level == 10)
        return;

    for (int i = 1; i <= 4; i++) {
        arr[level] = i;
        gen(level + 1);
    }
}

public static void main(String[] args)  {
    gen(0);
}

Но если вы заботитесь о заказе, используйте это: 

private static int top;
private static int[] arr = new int[10]; 

public static void gen(int level) {
    if (level == top) {

        for (int i = 0; i < level; i++)
            System.out.print(arr[i] + " ");
        System.out.println();

        return;
    }

    for (int i = 1; i <= 4; i++) {
        arr[level] = i;
        gen(level + 1);
    }
}

public static void main(String[] args)  {
    for (top = 1; top <= 10; top++)
        gen(0);
}
...