Задачка из комбинаторики.

Правильно же.

К сожалению я определил это практически путём перебора и сначала думал что нужно делать по одной из формул (n над k). Прошу объяснить почему я неправильно думаю :) И помочь немного с кодом.

Всего есть n! различных обычных перестановок и 2^n способов расставить знаки. Поскольку каждая пара из перестановки и способа-расставить-знаки дает уникальную перестановку-со-знаками, эти количества нужно перемножить. Вот и получаем (2^n)*n!

Спасибо, на самом деле мне это должно было быть очевидно. Осталось теперь придумать алгоритм эффективной генерации перестановок. Должно же быть что-то, чтобы избежать 2^n вызовов функции генерации перестановок.

p.s. как называется эта формула?

как называется эта формула?

Никак. Подобные формулы получают по мере надобности, собственных имен они недостойны.

Должно же быть что-то, чтобы избежать 2^n вызовов функции генерации перестановок.

Для каждой из n! перестановок перебираешь 2^n способов расставить знаки. В чем проблема?

В чем проблема?

Пока не придумал как написать код для расстановки знаков 2^n способами.

Есть алгоритм перебора всех двоичных чисел до n-го разряда за минимальное количество «изменений», возьми 0 за +, а 1 за - и получишь 2^n способов.

Пока не придумал как написать код для расстановки знаков 2^n способами.

Набор из n знаков можно отождествить с n-битным целым числом: если i-тый знак - «плюс», то i-тый бит равен нулю; если i-тый знак - «минус», то i-тый бит равен единице.

Так что задача сводится к тому, чтобы перечислить целые от 0 до 2^n-1.

Спасибо! Именно в этом была проблема, не догадался что так можно.