Получение нескольких строк с повторяющимся символом [duplicate]

Конкретный пример, который я использовал студентам, заключается в том, что они должны писать

List myList = new ArrayList(); // programming to the List interface

вместо

ArrayList myList = new ArrayList(); // this is bad

. Они выглядят точно так же в короткой программе, но если вы продолжаете использовать myList 100 раз в своей программе, вы можете начать видеть разницу. Первая декларация гарантирует, что вы вызываете только методы на myList, которые определены интерфейсом List (поэтому нет специальных методов ArrayList). Если вы запрограммировали интерфейс таким образом, позже вы можете решить, что вам действительно нужно

List myList = new TreeList();

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

Выгоды еще более очевидны (я думаю), когда вы говорите о параметрах метода и возвращаемых значениях. Возьмем это, например:

public ArrayList doSomething(HashMap map);

Это объявление метода связывает вас с двумя конкретными реализациями (ArrayList и HashMap). Как только этот метод вызывается из другого кода, любые изменения этих типов, вероятно, означают, что вам также придется изменить код вызова. Было бы лучше запрограммировать интерфейсы.

public List doSomething(Map map);

Теперь не имеет значения, какой тип List вы возвращаете или какой Map передается в качестве параметра. Изменения, внесенные вами в метод doSomething, не заставят вас изменить код вызова.

34
задан sashoalm 14 August 2015 в 06:50
поделиться

14 ответов

Проверьте этот код.

    #include<stdio.h>

    //it can be done by recursion

    void func(int *flag, int *num, int n){  //take 'n' to count the number of digits
        int i;
        if(n==9){                           //if n=9 then print the number
            for(i=0;i<n;i++)
                printf("%d",num[i]);
            printf("\n");
        }
        for(i=1;i<=9;i++){

            //put the digits into the array one by one and send if for next level

            if(flag[i-1]==0){
                num[n]=i;
                flag[i-1]=1;
                func(flag,num,n+1);
                flag[i-1]=0;
            }
        }
    }

    //here is the MAIN function
    main(){

        int i,flag[9],num[9];
        for(i=0;i<9;i++)        //take a flag to avoid repetition of digits in a number
            flag[i]=0;          //initialize the flags with 0

        func(flag,num,0);       //call the function

        return 0;
    }

Если у вас есть какие-либо вопросы, не стесняйтесь спрашивать.

6
ответ дан biswasJUCSE 22 August 2018 в 23:43
поделиться

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

#include <stdio.h>

static int step(const char *str, int n, const char *set) {
    char buf[n + 2];
    int i, j, count;

    if (*set) {
        /* insert the first character from `set` in all possible
         * positions in string `str` and recurse for the next
         * character.
         */
        for (count = 0, i = n; i >= 0; i--) {
            for (j = 0; j < i; j++)
                buf[j] = str[j];
            buf[j++] = *set;
            for (; j <= n; j++)
                buf[j] = str[j - 1];
            buf[j] = '\0';
            count += step(buf, n + 1, set + 1);
        }
    } else {
        printf("%s\n", str);
        count = 1;
    }
    return count;
}

int main(int argc, char **argv) {
    int total = step("", 0, argc > 1 ? argv[1] : "123456789");
    printf("%d combinations\n", total);
    return 0;
}

Он использует рекурсию, но не бит-маски и может использоваться для любого набора символов. Он также вычисляет количество перестановок, поэтому вы можете проверить, что он производит факториальные (n) перестановки для набора из n символов.

8
ответ дан chqrlie 22 August 2018 в 23:43
поделиться

итеративная версия, которая широко использует биты

, отмечает, что array можно изменить на любой тип и установить в любом порядке, это «подсчет» цифр в заданном порядке

Для более подробного объяснения посмотрите мой первый ответ (который менее гибкий, но гораздо более быстрый) https://stackoverflow.com/a/31928246/2963099

Чтобы сделать его итеративным , необходимы массивы для сохранения состояния на каждом уровне

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

int bit_val(unsigned int v) {
  static const int MultiplyDeBruijnBitPosition2[32] = {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return MultiplyDeBruijnBitPosition2[(unsigned int)(v * 0x077CB531U) >> 27];
}

void uniq_digits(const int array[], const int length) {
  unsigned int unused[length-1];                    // unused prior
  unsigned int combos[length-1];                    // digits untried
  int digit[length];                                // printable digit
  int mult[length];                                 // faster calcs
  mult[length-1]=1;                                 // start at 1
  for (int i = length-2; i >= 0; --i)
     mult[i]=mult[i+1]*10;                          // store multiplier
  unused[0]=combos[0]=((1<<(length))-1);            // set all bits 0-length
  int depth=0;                                      // start at top
  digit[0]=0;                                       // start at 0
  while(1) {
    if (combos[depth]) {                            // if bits left
      unsigned int avail=combos[depth];             // save old
      combos[depth]=avail & (avail-1);              // remove lowest bit
      unsigned int bit=avail-combos[depth];         // get lowest bit
      digit[depth+1]=digit[depth]+mult[depth]*array[bit_val(bit)]; // get associated digit
      unsigned int rest=unused[depth]&(~bit);       // all remaining
      depth++;                                      // go to next digit
      if (depth!=length-1) {                        // not at bottom
        unused[depth]=combos[depth]=rest;           // try remaining
      } else {
        show(digit[depth]+array[bit_val(rest)]);    // print it
        depth--;                                    // stay on same level
      }
    } else {
      depth--;                                      // go back up a level
      if (depth < 0)
        break;                                      // all done
    }
  }
}

. Некоторые тайминги с использованием только 1 до 9 с 1000 повторений:

6
ответ дан Community 22 August 2018 в 23:43
поделиться
  • 1
    Я понятия не имею, как работают биты и как это работает. – Jack Swanson 5 August 2015 в 08:55
  • 2
    Назначение bit отображает значение num в значения 1, 2, 4, 8 и т. Д. В соответствии со значением digit (0, 1, 2, 3 и т. Д.). Кто-то может показать более краткий пример, но такой подход довольно распространен в системном программировании с C. – Thomas Dickey 5 August 2015 в 09:33
  • 3
    Mind time my 2nd solution (после EDIT , полностью развернутого) Просто интересно, если ваши результаты синхронизации совпадают с моими, плюс имеет смысл иметь независимую проверку: stackoverflow.com/a/31928246/ 2963099 – Glenn Teitelbaum 12 August 2015 в 17:42
  • 4
    Комментарии в вопросе указывают, что ноль не является действительной цифрой в результате. Желательны только 1-9. – Speed8ump 13 August 2015 в 22:56
  • 5
    @ThomasDickey Ницца! Какой из моих ответов вы проверили? Маска одна, check1 () или массив один, check2 ()? Не могли бы вы проверить оба? У меня есть чувство, которое будет быстрее, но было бы неплохо подтвердить. – George André 14 August 2015 в 08:02
  • 6
    Добавлен ifdef для включения 0s – Glenn Teitelbaum 16 August 2015 в 15:02
  • 7
    @ это вот общая итеративная версия, ее в два раза медленнее, чем у моей другой, но здесь вы идете – Glenn Teitelbaum 17 August 2015 в 21:12
  • 8
    @ThomasDickey: не могли бы вы добавить мое решение в зал славы? Я думаю, что это довольно быстро. – wildplasser 17 August 2015 в 23:28
  • 9
    Перемещено EDIT вверх – Glenn Teitelbaum 18 August 2015 в 17:43
  • 10
    Вы сравниваете яблоки с апельсинами. Ваша функция выводит каждое возможное значение за один вызов, а каждое другое решение выводит одно значение. Как вы этого не заметили. Даже игнорируя то, что я серьезно сомневаюсь в правильности вашей методики измерения. – this 18 August 2015 в 18:38
  • 11
    Напишите функцию, которая принимает массив и его длину, как функция nextPermutation, и записывает следующее значение в массив и возвращает. Тогда попробуйте сравнить. – this 18 August 2015 в 18:40
  • 12
    @ это OP было сгенерировано все, рекурсивное генерирует все, у swap был код для генерации всех, у nextPermutation была основная функция, которая генерировала все. И если вы сомневаетесь в моих методах, запустите его. Требовалось не создавать следующего, умного, как это было. Моя развернутая рекурсия по-прежнему является самой быстрой при решении требования OP, используя шаблоны и std::bitset в C ++, я мог бы двигаться быстрее, но это C – Glenn Teitelbaum 18 August 2015 в 20:20
  • 13
    Ваши функции могут быть самыми быстрыми, по вашим измерениям, но вы видите, что если вы определили OUTPUT, функция не вернется или не напишет нигде. Результат просто потерян. Хм, другие функции, похоже, возвращают результат каждый раз, когда их вызывают. Это и тот факт, что каждая другая функция может быть изменена, поэтому она вычисляет каждое значение внутри, а не вызывается в цикле с дополнительными накладными расходами, делает вашу запись недействительной. До свидания. – this 18 August 2015 в 20:34

Здесь много длинных фрагментов кода. Лучше думать больше и меньше кода.

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

Как бы вы это сделали без кода? Получите 10 карт и напишите цифры от 0 до 9. Нарисуйте строку из 9 квадратов на столе. Выберите карту. Поместите его в первый квадрат, другой во второй и т. Д. Когда вы выбрали 9, у вас есть свой первый номер. Теперь удалите последнюю карту и замените ее каждой возможной альтернативой. (В этом случае всего 1). Каждый раз, когда все квадраты заполняются, у вас есть еще один номер. Когда вы сделали все альтернативы для последнего квадрата, сделайте это для последнего 2. Повторите с последними 3 и т. Д., Пока вы не рассмотрите все альтернативы для всех ящиков.

Написание сжатой программы для этого - выбор простых структур данных. Используйте массив символов для строки из 9 квадратных.

Используйте другой массив для набора карт. Чтобы удалить элемент из набора размера N, хранящегося в массиве A [0 .. N-1], мы используем старый трюк. Скажем, элемент, который вы хотите удалить, - A [I]. Сохраните значение A [I] в сторону. Затем скопируйте последний элемент A [N-1] «вниз», переписывая A [I]. Новый набор A [0 .. N-2]. Это прекрасно работает, потому что нас не интересует порядок в наборе.

Остальное - использовать рекурсивное мышление для перечисления всех возможных альтернатив. Если я знаю, как найти все варианты из набора символов размера M в строку размера N, то для получения алгоритма просто выберите каждый возможный символ для первой позиции строки, затем повторите выбор, чтобы выбрать остальную часть N-1 символов из оставшегося набора размеров M-1. Мы получаем хорошую 12-строчную функцию:

#include <stdio.h>

// Select each element from the given set into buf[pos], then recur
// to select the rest into pos+1... until the buffer is full, when
// we print it.
void select(char *buf, int pos, int len, char *set, int n_elts) {
  if (pos >= len)
    printf("%.*s\n", len, buf);  // print the full buffer
  else
    for (int i = 0; i < n_elts; i++) {
      buf[pos] = set[i];         // select set[i] into buf[pos]
      set[i] = set[n_elts - 1];  // remove set[i] from the set
      select(buf, pos + 1, len, set, n_elts - 1); // recur to pick the rest
      set[n_elts - 1] = set[i];  // undo for next iteration
      set[i] = buf[pos];
    }
}

int main(void) {
  char buf[9], set[] = "0123456789";
  select(buf, 0, 9, set, 10); // select 9 characters from a set of 10
  return 0;
}

Вы не упомянули, нормально ли положить ноль в первую позицию. Предположим, что это не так. Поскольку мы хорошо понимаем алгоритм, легко избежать выбора нуля в первую позицию. Просто пропустите эту возможность, заметив, что !pos в C имеет значение 1, если pos равно 0 и 0. Если вам не нравится эта слегка неясная идиома, попробуйте (pos == 0 ? 1 : 0) как более читаемую замену:

#include <stdio.h>

void select(char *buf, int pos, int len, char *set, int n_elts) {
  if (pos >= len)
    printf("%.*s\n", len, buf);
  else
    for (int i = !pos; i < n_elts; i++) {
      buf[pos] = set[i];
      set[i] = set[n_elts - 1];
      select(buf, pos + 1, len, set, n_elts - 1);
      set[n_elts - 1] = set[i];
      set[i] = buf[pos];
    }
}

int main(void) {
  char buf[9], set[] = "0123456789";
  select(buf, 0, 9, set, 10);
  return 0;
}
7
ответ дан Gene 22 August 2018 в 23:43
поделиться

Вы можете использовать маску для установки флагов, причем флаги будут содержать цифру, уже указанную в номере или нет. Например:

int mask = 0x0, j;

for(j= 1; j<=9; j++){
    if(mask & 1<<(input%10))
        return 0;
    else
        mask |= 1<<(input%10);
    input /= 10;
}
return !(mask & 1);

Полная программа:

    #include <stdio.h>

int check(int input)
{
    int mask = 0x0, j;

    for(j= 1; j<=9; j++){
        if(mask & 1<<(input%10))
            return 0;
        else
            mask |= 1<<(input%10);
        input /= 10;
    }
    /* At this point all digits are unique
     We're not interested in zero, though */
    return !(mask & 1);
}

int main()
{
    int indx;
    for( indx = 123456789; indx <=987654321; indx++){
        if( check(indx) )
            printf("%d\n",indx);
    }
}

Отредактировано ...

Или вы можете сделать то же самое с массивом:

int check2(int input)
{
    int j, arr[10] = {0,0,0,0,0,0,0,0,0,0};

    for(j=1; j<=9; j++) {
        if( (arr[input%10]++) || (input%10 == 0) )
            return 0;
        input /= 10;
    }
    return 1;
}
6
ответ дан George André 22 August 2018 в 23:43
поделиться
  • 1
    Я, честно говоря, не знаю, как подойти к битам, поскольку я их никогда не узнавал. Есть ли еще один способ сделать это? – Jack Swanson 5 August 2015 в 08:56
  • 2
    @RichardFlores Извините, это самый быстрый и требует меньше кода. Это хороший урок о и, или и бит, манипуляции. Я бы рекомендовал вернуться к этому примеру, когда вы узнаете об этих полях. Теоретически вы можете заменить маску массивом целых чисел, имеющих тот же результат. – George André 5 August 2015 в 08:59
  • 3
    @RichardFlores Я обновил свой ответ с примером массива вместо этого, как вы просили. :) – George André 5 August 2015 в 09:06
  • 4
    @RichardFlores получается версия массива немного быстрее ... :) – George André 5 August 2015 в 09:11
  • 5
    Спасибо. В чем именно заключается эта логика? – Jack Swanson 5 August 2015 в 09:16

Вот один из подходов - начните с массива уникальных цифр, затем произвольно перетасуйте их:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int main( void )
{
  char digits[] = "123456789";

  srand( time( NULL ) );

  size_t i = sizeof digits - 1;
  while( i )
  {
    size_t j = rand() % i;
    char tmp = digits[--i];
    digits[i] = digits[j];
    digits[j] = tmp;
  }

  printf( "number is %s\n", digits );
  return 0;
}

Некоторые выходные данные:

john@marvin:~/Development/snippets$ ./nine
number is 249316578
john@marvin:~/Development/snippets$ ./nine
number is 928751643
john@marvin:~/Development/snippets$ ./nine
number is 621754893
john@marvin:~/Development/snippets$ ./nine
number is 317529864

Обратите внимание, что это символьные строки уникальных десятичных цифр, а не числовые значения; если вы хотите получить соответствующее целочисленное значение, вам необходимо выполнить преобразование, например

long val = strtol( digits, NULL, 10 );
6
ответ дан John Bode 22 August 2018 в 23:43
поделиться

Вот немного уродливое, но очень быстрое решение с использованием вложенных for loops.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define NINE_FACTORIAL  362880

int main(void) {

  //array where numbers would be saved
  uint32_t* unique_numbers = malloc( NINE_FACTORIAL * sizeof(uint32_t) );
  if( !unique_numbers ) {
    printf("Could not allocate memory for the Unique Numbers array.\n");
    exit(1);
  }

  uint32_t n = 0;
  int a,b,c,d,e,f,g,h,i;

  for(a = 1; a < 10; a++) {
    for(b = 1; b < 10; b++) {
    if (b == a) continue;

      for(c = 1; c < 10; c++) {
      if(c==a || c==b) continue;

        for(d = 1; d < 10; d++) {
        if(d==a || d==b || d==c) continue;

          for(e = 1; e < 10; e++) {
          if(e==a || e==b || e==c || e==d) continue;

            for(f = 1; f < 10; f++) {
            if (f==a || f==b || f==c || f==d || f==e) 
                                continue;

              for(g = 1; g < 10; g++) {
              if(g==a || g==b || g==c || g==d || g==e 
                      || g==f) continue;

                for(h = 1; h < 10; h++) {
                if (h==a || h==b || h==c || h==d || 
                 h==e || h==f || h==g) continue;

                  for(i = 1; i < 10; i++) {
                  if (i==a || i==b || i==c || i==d || 
                  i==e || i==f || i==g || i==h) continue;

                  // print the number or
                  // store the number in the array
                  unique_numbers[n++] = a * 100000000
                        + b * 10000000
                        + c * 1000000
                        + d * 100000
                        + e * 10000
                        + f * 1000
                        + g * 100
                        + h * 10
                        + i;

                  }
                }
              }
            }
          }
        }
      }
    }
  }


  // do stuff with unique_numbers array
  // n contains the number of elements

  free(unique_numbers);

  return 0;
}

То же самое с использованием некоторых макросов.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define l_(b,n,c,p,f) { int i; for(i = 1; i < 10; i++) {            \
      int j,r=0; for(j=0;j<p;j++){if(i == c[j]){r=1;break;}}        \
      if(r) continue; c[p] = i; f   } }

#define l_8(b,n,c,p) {                                              \
    int i; for(i=1; i< 10; i++) {int j, r=0;                        \
      for(j=0; j<p; j++) {if(i == c[j]) {r = 1; break;}}            \
      if(r)continue; b[n++] = c[0] * 100000000  + c[1] * 10000000   \
            + c[2] * 1000000 + c[3] * 100000 + c[4] * 10000         \
            + c[5] * 1000 + c[6] * 100 + c[7] * 10 + i; } }

#define l_7(b,n,c,p) l_(b,n,c,p, l_8(b,n,c,8))
#define l_6(b,n,c,p) l_(b,n,c,p, l_7(b,n,c,7))
#define l_5(b,n,c,p) l_(b,n,c,p, l_6(b,n,c,6))
#define l_4(b,n,c,p) l_(b,n,c,p, l_5(b,n,c,5))
#define l_3(b,n,c,p) l_(b,n,c,p, l_4(b,n,c,4))
#define l_2(b,n,c,p) l_(b,n,c,p, l_3(b,n,c,3))
#define l_1(b,n,c,p) l_(b,n,c,p, l_2(b,n,c,2))

#define get_unique_numbers(b,n,c) do {int i; for(i=1; i<10; i++) { \
      c[0] = i; l_1(b,n,c,1) } } while(0)


#define NINE_FACTORIAL  362880

int main(void) {

  //array where numbers would be saved
  uint32_t* unique_numbers = malloc( NINE_FACTORIAL * sizeof(uint32_t) );
  if( !unique_numbers ) {
    printf("Could not allocate memory for the Unique Numbers array.\n");
    exit(1);
  }

  int n = 0;
  int current_number[8] = {0};

  get_unique_numbers(unique_numbers, n, current_number);


  // do stuff with unique_numbers array
  // NINE_FACTORIAL is the number of elements


  free(unique_numbers);

  return 0;
}

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

5
ответ дан MiJo 22 August 2018 в 23:43
поделиться
47
ответ дан Nominal Animal 22 August 2018 в 23:43
поделиться

Здесь хорошо работает рекурсия.

#include <stdio.h>

void uniq_digits(int places, int prefix, int mask) {
  if (!places) {
    printf("%d\n", prefix);
    return;
  }
  for (int i = 0; i < 10; i++) {
    if (prefix==0 && i==0) continue;
    if ((1<<i)&mask) continue;
    uniq_digits(places-1, prefix*10+i, mask|(1<<i)); 
  }
}

int main(int argc, char**argv) {
  uniq_digits(9, 0, 0);
  return 0;
}
12
ответ дан Paul Hankin 22 August 2018 в 23:43
поделиться

Простым способом является создание массива с девятью различными значениями, перетасовка и печать перетасованного массива. Повторяйте столько раз, сколько необходимо. Например, используя стандартную функцию rand() в качестве основы для перетасовки ...

#include <stdlib.h>     /*  for srand() and rand */
#include <time.h>       /*  for time() */
#include <stdio.h>      

#define SIZE 10     /*   size of working array.  There are 10 numeric digits, so ....   */
#define LENGTH 9    /*  number of digits we want to output.  Must not exceed SIZE */
#define NUMBER 12   /*  number of LENGTH digit values we want to output */

void shuffle(char *buffer, int size)
{
     int i;
     char temp;
     for (i=size-1; i>0; --i)
     {
          /*  not best way to get a random value of j in [0, size-1] but
               sufficient for illustrative purposes
          */
          int j = rand()%size;
          /* swap buffer[i] and buffer[j] */
          temp = buffer[i];    
          buffer[i] = buffer[j];
          buffer[j] = temp;
     }
}

void printout(char *buffer, int length)
{
      /*  this assumes SIZE <= 10 and length <= SIZE */

      int i;
      for (i = 0; i < length; ++i)
          printf("%d", (int)buffer[i]);
      printf("\n");
}

int main()
{
     char buffer[SIZE];
     int i;
     srand((unsigned)time(NULL));   /*  seed for rand(), once and only once */

     for (i = 0; i < SIZE; ++i)  buffer[i] = (char)i;  /*  initialise buffer */

     for (i = 0; i < NUMBER; ++i)
     {
         /*  keep shuffling until first value in buffer is non-zero */

         do shuffle(buffer, SIZE); while (buffer[0] == 0);
         printout(buffer, LENGTH);
     }
     return 0;
}

Это выводит ряд строк на stdout, каждый из которых содержит 9 уникальных цифр. Обратите внимание, что это не предотвращает дублирование.

5
ответ дан Peter 22 August 2018 в 23:43
поделиться

Я рекомендую ответить для номинанта , но если вы только генерируете это значение, чтобы вы могли его распечатать, вы можете устранить часть работы и в то же время получить более общую процедуру, используя тот же method:

char *shuffle( char *digit, int digits, int count, unsigned int seed )
{
    //optional: do some validation on digit string
    //  ASSERT(digits == strlen(digit));
    //optional: validate seed value is reasonable
    //  for(unsigned int badseed=1, x=digits, y=count; y > 0; x--, y--)
    //      badseed *= x;
    //  ASSERT(seed < badseed);

    char *work = digit;
    while(count--)
    {
        int i = seed % digits;
        seed /= digits--;
        unsigned char selectedDigit = work[i];
        work[i] = work[0];
        work[0] = selectedDigit;
        work++;
    }
    work[0] = 0;

    //seed should be zero here, else the seed contained extra information
    return digit;
}

Этот метод является деструктивным по цифрам, которые в действительности не должны быть числовыми или уникальными в этом отношении.

вы хотите, чтобы выходные значения, сгенерированные в отсортированном возрастающем порядке, немного больше работали:

char *shuffle_ordered( char *digit, int digits, int count, unsigned int seed )
{
    char *work = digit;
    int doneDigits = 0; 
    while(doneDigits < count)
    {
        int i = seed % digits;
        seed /= digits--;
        unsigned char selectedDigit = work[i];
        //move completed digits plus digits preceeding selectedDigit over one place
        memmove(digit+1,digit,doneDigits+i);
        digit[0] = selectedDigit;
        work++;
    }
    work[0] = 0;

    //seed should be zero here, else the seed contained extra information
    return digit;
}

В любом случае это называется так:

for(unsigned int seed = 0; seed < 16*15*14; ++seed)
{
    char work[] = "0123456789ABCDEF";
    printf("seed=%d -> %s\n",shuffle_ordered(work,16,3,seed));
}

Это должно распечатать упорядоченный список трехзначных шестнадцатеричных значений без дублированных цифр:

seed 0 -> 012
seed 1 -> 013
...
seed 3358 -> FEC
seed 3359 -> FED

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

6
ответ дан Speed8ump 22 August 2018 в 23:43
поделиться

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

int main( void )
{
    int array[] = { 1, 2, 3 };
    int length = sizeof(array) / sizeof(int);

    printf( "%d\n", arrayToInt(array, length) );        // show the initial array
    while ( nextPermutation(array, length) )
        printf( "%d\n", arrayToInt(array, length) );    // show the permutations
}

будет генерировать этот выход

123
132
213
231
312
321

, и если вы измените array на

int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

, тогда код будет генерировать и отображать все 362880 перестановок этих девяти чисел в порядке возрастания.


Функция nextPermutation имеет три шага

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

. Позвольте мне проиллюстрировать пример. Предположим, что в массиве есть числа в этом порядке

1 9 5 4 8 7 6 3 2

. На первом этапе будет найден 4. Поскольку 8 7 6 3 2 находятся в порядке убывания, 4 - это первое число (начиная с конца массива), за которым следует большее число.

На втором этапе 6 , так как 6 - это первое число (начиная с конца массива), которое больше 4. После замены 4 и 6 массив выглядит так

1 9 5 6 8 7 4 3 2

Обратите внимание, что все числа справа от 6 находятся в порядке убывания. Переключение 6 и 4 не изменило того факта, что последние пять чисел в массиве находятся в порядке убывания.

Последний шаг заключается в замене чисел после 6, поэтому что они все в порядке возрастания. Поскольку мы знаем, что числа находятся в порядке убывания, все, что нам нужно сделать, - это обмен файлами 8 с 2 и 7 с 3. Результирующий массив -

1 9 5 6 2 3 4 7 8

. Поэтому при любой перестановке чисел функция найдет следующую перестановку, просто заменив несколько чисел. Единственным исключением является последняя перестановка, которая имеет все числа в обратном порядке, т. Е. 9 8 7 6 5 4 3 2 1. В этом случае шаг 1 терпит неудачу, и функция возвращает 0, чтобы указать, что больше нет перестановок.


Итак, вот функция nextPermutation

int nextPermutation( int array[], int length )
{
    int i, j, temp;

    // starting from the end of the array, find the first number (call it 'x')
    // that is followed by a larger number
    for ( i = length - 2; i >= 0; i-- )
        if ( array[i] < array[i+1] )
            break;

    // if no such number was found (all the number are in reverse order)
    // then there are no more permutations
    if ( i < 0 )
        return 0;

    // starting from the end of the array, find the first number (call it 'y')
    // that is larger than 'x', and swap 'x' and 'y'
    for ( j = length - 1; j > i; j-- )
        if ( array[j] > array[i] )
        {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            break;
        }

    // 'y' is now where 'x' was, and all of the numbers to the right of 'y'
    // are in descending order, swap them so that they are in ascending order
    for ( i++, j = length - 1; j > i; i++, j-- )
    {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    return 1;
}

Обратите внимание, что функция nextPermutation работает для любого массива чисел (номера не обязательно должны быть последовательными ). Например, если начальный массив

int array[] = { 2, 3, 7, 9 };

, то функция nextPermutation найдет все перестановки 2,3,7 и 9.


Просто для полноты, вот функция arrayToInt, которая использовалась в функции main. Эта функция предназначена только для демонстрационных целей. Он предполагает, что массив содержит только цифры с одной цифрой и не требует проверки на переполнение. Он будет работать для 9-значного числа при условии, что int не менее 32 бит.

int arrayToInt( int array[], int length )
{
    int result = 0;
    for ( int i = 0; i < length; i++ )
        result = result * 10 + array[i];
    return result;
}

Так как, кажется, некоторый интерес к производительности этого алгоритма, здесь некоторые цифры:

length= 2 perms=        2 (swaps=        1 ratio=0.500) time=   0.000msec
length= 3 perms=        6 (swaps=        7 ratio=1.167) time=   0.000msec
length= 4 perms=       24 (swaps=       34 ratio=1.417) time=   0.000msec
length= 5 perms=      120 (swaps=      182 ratio=1.517) time=   0.001msec
length= 6 perms=      720 (swaps=     1107 ratio=1.538) time=   0.004msec
length= 7 perms=     5040 (swaps=     7773 ratio=1.542) time=   0.025msec
length= 8 perms=    40320 (swaps=    62212 ratio=1.543) time=   0.198msec
length= 9 perms=   362880 (swaps=   559948 ratio=1.543) time=   1.782msec
length=10 perms=  3628800 (swaps=  5599525 ratio=1.543) time=  16.031msec
length=11 perms= 39916800 (swaps= 61594835 ratio=1.543) time= 170.862msec
length=12 perms=479001600 (swaps=739138086 ratio=1.543) time=2036.578msec

ЦП для теста был 2,5 ГГц Intel i5-процессором. Алгоритм генерирует около 200 миллионов перестановок в секунду и занимает менее 2 миллисекунд для генерации всех перестановок из 9 чисел.

Интересно также, что в среднем для алгоритма требуется всего 1,5 своп в секунду перестановка. Половина времени алгоритм просто заменяет последние два числа в массиве. В 11 из 24 случаев алгоритм выполняет два свопа. Таким образом, только в 1 из 24 случаев алгоритм нуждается в более чем двух свопах.

Наконец, я попробовал алгоритм со следующими двумя массивами

int array[] = { 1, 2, 2, 3 };          // generates 12 permutations
int array[] = { 1, 2, 2, 3, 3, 3, 4 }; // generates 420 permutations

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

14
ответ дан user3386109 22 August 2018 в 23:43
поделиться
  • 1
    Отлично сработано. Кодекс / решение - мили впереди конкурентов. – this 14 August 2015 в 17:07
  • 2
    Используя простые массивы, чтобы получить самый быстрый и читаемый ответ, сравните его с другими решениями. Интересно, вы сами выяснили процедуру? – this 14 August 2015 в 18:32
  • 3
    @this Yup, мне нужен способ генерации перестановок без рекурсии. Поэтому я начал с печати перестановок для коротких массивов (с использованием рекурсии), а затем проанализировал вывод, чтобы найти шаблон. Оказывается, что шаблон достаточно прост, что я смог перевести его в код. – user3386109 14 August 2015 в 20:05
  • 4
    @GlennTeitelbaum У вас нет нерекурсивного решения. Я бы с удовольствием ее протестировал. Пожалуйста, напишите версию с общественным прототипом: ( int array[], int length ) – this 16 August 2015 в 13:43
  • 5
    @GlennTeitelbaum: Последовательность допускает постоянную перестановку любой строки без рекурсии. Вам нужно выполнить парные свопы в порядке этой последовательности. (Таким образом, ровно одна своп на перестановку, таким образом, постоянное время. Генерация всех перестановок - это, конечно, O (N!), Взяв ровно N! -1 swaps.) Я не знаю, имеет ли эта последовательность имя. – Nominal Animal 19 August 2015 в 00:51

Немного поздно для вечеринки, но очень быстро (30 мс здесь) ...

#include <stdio.h>
#define COUNT 9

   /* this buffer is global. intentionally.
   ** It occupies (part of) one cache slot,
   ** and any reference to it is a constant
   */
char ten[COUNT+1] ;

unsigned rec(unsigned pos, unsigned mask);
int main(void)
{
unsigned res;

ten[COUNT] = 0;

res = rec(0, (1u << COUNT)-1);
fprintf(stderr, "Res=%u\n", res);

return 0;
}

/* recursive function: consume the mask of available numbers
** until none is left.
** return value is the number of generated permutations.
*/
unsigned rec(unsigned pos, unsigned mask)
{
unsigned bit, res = 0;

if (!mask) { puts(ten); return 1; }

for (bit=0; bit < COUNT; bit++) {
        if (! (mask & (1u <<bit)) ) continue;
        ten[pos] = '1' + bit;
        res += rec(pos+1, mask & ~(1u <<bit));
        }
return res;
}
0
ответ дан wildplasser 22 August 2018 в 23:43
поделиться
6
ответ дан Community 5 November 2018 в 21:19
поделиться
Другие вопросы по тегам:

Похожие вопросы: