Сделать ноль из первых чисел

15

Вызов

Задача состоит в том, чтобы написать код, который принимает положительное целое число n в качестве входных данных и отображает все возможные способы записи чисел от 1 до n с положительным или отрицательным знаком между ними, так что их сумма равна равно нулю. Пожалуйста, помните, что вы можете использовать только сложение или вычитание.

Например, если введено 3, то есть 2 способа сделать сумму 0:

 1+2-3=0
-1-2+3=0

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

Теперь 3 было довольно просто. Давайте перечислим все способы, когда мы рассмотрим число 7.

 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

Итак, у нас есть 8 возможных способов.


Вход и выход

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

Также вы можете распечатать вывод в любом формате, который вам нравится . Но это должно быть понятно . Например, вы можете распечатать его как в примере выше. Или вы можете просто распечатать знаки чисел по порядку. В противном случае вы также можете вывести «0» и «1» по порядку, где «0» будет отображать отрицательный знак, а «1» будет отображать положительный знак (или наоборот).

Например, вы можете представить 1 + 2-3 = 0, используя:

1+2-3=0
1+2-3
[1,2,-3]
++-
110
001    

Однако я бы порекомендовал использовать любой из первых трех форматов для простоты. Вы можете считать все входные данные действительными.


Примеры

7 ->

 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

4 ->

 1-2-3+4=0
-1+2+3-4=0

2 -> -

8 ->

 1+2+3+4-5-6-7+8=0
 1+2+3-4+5-6+7-8=0
 1+2-3+4+5+6-7-8=0
 1+2-3-4-5-6+7+8=0
 1-2+3-4-5+6-7+8=0
 1-2-3+4+5-6-7+8=0
 1-2-3+4-5+6+7-8=0
-1+2+3-4+5-6-7+8=0
-1+2+3-4-5+6+7-8=0
-1+2-3+4+5-6+7-8=0
-1-2+3+4+5+6-7-8=0
-1-2+3-4-5-6+7+8=0
-1-2-3+4-5+6-7+8=0
-1-2-3-4+5+6+7-8=0

счет

Это , поэтому выигрывает самый короткий код!

Маниш Кунду
источник
Обратите внимание, что это не обман кода codegolf.stackexchange.com/questions/8655/… , поскольку этот вызов предназначен для того, чтобы принимать только n в качестве входных данных и использовать все числа 1-n по порядку.
Маниш Кунду
Можем ли мы представлять +как Nи -как -N, или это заходит слишком далеко? (например 3-> [[-3,-3,3], [3,3,-3]])
Джонатан Аллан
@JonathanAllan Разве это не упоминается в списке форматов вывода? Или я неправильно истолковал твой вопрос?
Маниш Кунду
Я имею в виду, как 0и 1вариант, но с использованием Nи -N(см. Мое редактирование выше)
Джонатан Аллан
2
@JonathanAllan Да, это конечно разрешено. Обязательно укажите это в ответе.
Маниш Кунду

Ответы:

5

Желе , 9 байт

1,-ṗ×RSÐḟ

Попробуйте онлайн!

Exp

1,-ṗ×RSÐḟ  Main link. Input = n. Assume n=2.
1,-        Literal list [1, -1].
   ṗ       Cartesian power n. Get [[1, 1], [1, -1], [-1, 1], [-1, -1]]
    ×R     Multiply (each list) by Range 1..n.
       Ðḟ  ilter out lists with truthy (nonzero)
      S      Sum.

Желе , 9 байт

По предложению Джонатана Аллана выведите список признаков.

1,-ṗæ.ÐḟR

Попробуйте онлайн!

user202729
источник
1
Как насчет (ab?) Использования формата вывода lax с ,Nṗæ.ÐḟR?
Джонатан Аллан
Или, в качестве альтернативы, это вывод результатов, умноженных на n.
user202729
NИ -Nвыход я предложил было разрешено, так что экономит один байт :) (просто нужно упомянуть формат в ответ)
Джонатан Аллана
3

Perl, 37 36 байт

perl -E 'map eval||say,glob join"{+,-}",0..<>' <<< 7
Тон Хоспел
источник
Красиво сделано. Вы можете отказаться, -nи <<<если вы замените $_на pop. Это на самом деле не улучшает ваш счет, но делает общее выражение короче;)
Chris
2

Шелуха , 10 байт

fo¬ΣΠmSe_ḣ

Попробуйте онлайн!

объяснение

Не слишком сложно.

fo¬ΣΠmSe_ḣ  Implicit input, say n=4
         ḣ  Range: [1,2,3,4]
     m      Map over the range:
      Se     pair element with
        _    its negation.
            Result: [[1,-1],[2,-2],[3,-3],[4,-4]]
    Π       Cartesian product: [[1,2,3,4],[1,2,3,-4],..,[-1,-2,-3,-4]]
f           Keep those
   Σ        whose sum
 o¬         is falsy (equals 0): [[-1,2,3,-4],[1,-2,-3,4]]
Zgarb
источник
1

Swift , 116 байт

func f(n:Int){var r=[[Int]()]
for i in 1...n{r=r.flatMap{[$0+[i],$0+[-i]]}}
print(r.filter{$0.reduce(0){$0+$1}==0})}

Попробуйте онлайн!

объяснение

func f(n:Int){
  var r=[[Int]()]                         // Initialize r with [[]]
                                          // (list with one empty list)
  for i in 1...n{                         // For i from 1 to n:
    r=r.flatMap{[$0+[i],$0+[-i]]}         //   Replace every list in r with the list
  }                                       //   prepended with i and prepended with -i
  print(r.filter{$0.reduce(0){$0+$1}==0}) // Print all lists in r that sums to 0
}
Герман Л
источник
1

Python 2 , 91 байт

lambda x:[s for s in[[~j*[1,-1][i>>j&1]for j in range(x)]for i in range(2**x)]if sum(s)==0]

Попробуйте онлайн!

Возвращает список удовлетворяющих списков (например, f (3) = [[- 1, -2,3], [1,2, -3]])

Час Браун
источник
1

C (GCC) , 171 байт

k,s;f(S,n,j)int*S;{if(j--)S[j]=~0,f(S,n,j),S[j]=1,f(S,n,j);else{for(s=k=0;k<n;k++)s+=S[k]*-~k;if(!s&&puts(""))for(k=0;k<n;)printf("%d",S[k++]+1);}}F(n){int S[n];f(S,n,n);}

Попробуйте онлайн! Используется 0для отрицательных и 2положительных признаков.

Джонатан Фрех
источник
1

Python 3 + numpy, 104 103 байта

import itertools as I,numpy as P
lambda N:[r for r in I.product(*[[-1,1]]*N)if sum(P.arange(N)*r+r)==0]

Выходные данные [-1, 1] соответствуют знаку.

user2699
источник
Вы можете убрать пробел раньше ifза -1 байт
ovs
0

JavaScript (ES6), 69 61 байт

Сэкономили 8 байтов, избавившись от k , как предложено @Neil

Печатает все решения с предупреждением () .

f=(n,o='')=>n?f(n-1,o+'+'+n)&f(n-1,o+'-'+n):eval(o)||alert(o)

Контрольные примеры

Использование console.log () вместо alert () для удобства пользователей.

Arnauld
источник
Тебе нужно k? Как то так:f=(n,o='')=>n?['+','-'].map(c=>f(n-1,c+n+o)):eval(o)||alert(o)
Нейл
@ Нил, я правда не ... Спасибо.
Арно
0

Сетчатка , 73 байта

.+
*
_
=_$`
+0`=
-$%"+
(-(_)+|\+(_)+)+
$&=$#2=$#3=
G`(=.+)\1=
=.*

_+
$.&

Попробуйте онлайн! Объяснение:

.+
*

Преобразовать ввод в унарный.

_
=_$`

Преобразуйте число в список =чисел с префиксом.

+0`=
-$%"+

Замените каждый =по очереди на оба -и +, дублируя количество строк каждый раз.

(-(_)+|\+(_)+)+
$&=$#2=$#3=

Отдельно посчитайте количество _s после -s и +s. Это сумма отрицательных и положительных чисел.

G`(=.+)\1=

Оставьте только те строки, где -s и +s отменяются.

=.*

Удалить счет.

_+
$.&

Преобразовать в десятичную.

Нил
источник
0

Perl 6 , 43 байта

{grep *.sum==0,[X] (1..$_ X*1,-1).rotor(2)}

Попробуйте это
Возвращает последовательность списков

Expanded:

{  # bare block lambda with implicit parameter 「$_」

  grep              # only return the ones
    *.sum == 0,     # that sum to zero

    [X]             # reduce with cross meta operator

      (
          1 .. $_   # Range from 1 to the input

        X*          # cross multiplied by

          1, -1

      ).rotor(2)    # take 2 at a time (positive and negative)
}

1..$_ X* 1,-1(1, -1, 2, -2)
(…).rotor(2)((1, -1), (2, -2))
[X] …((1, 2), (1, -2), (-1, 2), (-1, -2))

Брэд Гилберт b2gills
источник
0

J , 35 30 байт

-5 байт благодаря FrownyFrog!

>:@i.(]#~0=1#.*"1)_1^2#:@i.@^]

Попробуйте онлайн!

Оригинал:

J 35 байт

[:(#~0=+/"1)>:@i.*"1(_1^[:#:@i.2^])

Как это устроено

Я умножаю список 1..n на все возможные списки коэффициентов 1 / -1 и нахожу те, которые суммируются до нуля.

                    (             ) - the list of coefficients
                             i.     - list 0 to 
                               2^]  - 2 to the power of the input
                     _1^[:          - -1 to the power of 
                          #:@       - each binary digit of each number in 0..n-1 to 
                 *"1                - each row multiplied by
            >:@i.                   - list 1..n
  (#~      )                        - copy those rows
     0=+/"1                         - that add up to 0
[:                                  - compose   

Попробуйте онлайн!

В качестве альтернативы я попробовал явный глагол, используя подход декартового произведения +/-:

J 37 байт

3 :'(#~0=+/"1)(-y)]\;{(<"1@,.-)1+i.y'

{(<"1@,.-) находит декартовы произведения, например:

{(<"1@,.-) 1 2 3
┌───────┬────────┐
│1 2 3  │1 2 _3  │
├───────┼────────┤
│1 _2 3 │1 _2 _3 │
└───────┴────────┘

┌───────┬────────┐
│_1 2 3 │_1 2 _3 │
├───────┼────────┤
│_1 _2 3│_1 _2 _3│
└───────┴────────┘

Очень жаль, что он упаковывает результат, поэтому я потратил несколько байтов, чтобы распаковать значения

Попробуйте онлайн!

Гален Иванов
источник
@FrownyFrog Спасибо, я не был доволен правой стороной моего кода.
Гален Иванов