Конкретные комбинации элементов массива - PullRequest
Новая
       7

Конкретные комбинации элементов массива

0 голосов
/ 27 августа 2018

У меня есть двумерный массив значений строк:

ABC
-D-
-FG

где "-" означает пустое значение. Чего я хочу добиться, так это получить все комбинации элементов массива «слева направо», поэтому результаты данного массива должны быть:

ABC
АЦП
AFC
AFG
ABG
ADG

Пустые значения должны быть пропущены, а порядок элементов должен быть сохранен. Проблема в том, что количество столбцов и строк в массиве не фиксировано. Я пытался играть с циклом в цикле (и циклом) и рекурсией, но безуспешно. Кроме того, декартово произведение в этом случае бесполезно, так как будет создавать ненужные комбинации (я пытался динамически создавать временные таблицы sql и сохранять в них значения, создавая перекрестное соединение). Кто-нибудь может подсказать мне путь, пожалуйста?

1 Ответ

0 голосов
/ 29 августа 2018

Если я правильно понимаю ваши требования, вы можете сделать это, используя массив для хранения для каждого столбца индекса строки, содержащей значение для вывода. Первоначально этот массив будет содержать первую непустую строку для каждого столбца. На каждой итерации вы увеличиваете, начиная с самого нижнего столбца, индексируемую строку до тех пор, пока не получите непустое значение или не достигнете конца строк, и в этом случае вы возвращаете строку к первому непустому значению и перейдите к следующему столбцу. Это напоминает действие старого одометра в машине.

Вот некоторый Java-код для иллюстрации (извините, я не знаком с VB.Net) 

    char[][] values = {
            {'A', 'B', 'C'}, 
            {'-', 'D', '-'}, 
            {'-', 'F', 'G'}
            };

    int rows = values.length;
    int cols = values[0].length;

    int[] idx = new int[cols];

    // for each column, find the first non-empty character
    int i=0;
    for(; i<cols; i++)
    {
        while(idx[i] < rows && values[idx[i]][i] == '-') idx[i]++;
        if(idx[i] == rows) break;
    }

    // if a column was missing a non-empty value then we can't proceed
    if(i<cols) 
    {
        System.out.println("Missing value in column " + i);
        return;
    }

    while(true)
    {
        // print current solution
        for(int j=0; j<cols; j++) 
            System.out.print(values[idx[j]][j]);
        System.out.println();

        int k=0;
        for(; k<cols; k++)
        {
            // find next non-empty character
            do idx[k]++; while(idx[k] < rows && values[idx[k]][k] == '-');

            // if there was one, break
            if(idx[k] < rows) break;

            // else, wrap around to 0, but then find next non-empty row
            idx[k] = 0;
            while(values[idx[k]][k] == '-') idx[k]++;
        }

        // if the last index wrapped around then we're done
        if(k == cols) break;
    }

Выход: 

ABC
ADC
AFC
ABG
ADG
AFG
...