태그 보관물: set-partitions

set-partitions

술어에 실패한 항목을 계산하지 않고 크기가 지정된 청크로 목록을 분할하십시오. 일치해야합니다. 항목 : [], 크기 : 2,

자극 : 때로는 목록의 특정 항목이 총계에 포함되지 않습니다. 예를 들어, 아기가 부모의 무릎에 앉는 비행기 승객을 줄로 세는 것입니다.

도전 과제 : 항목 목록을 덩어리로 나누는 프로그램을 작성하십시오. 각 청크 (마지막은 제외)는 같은 크기입니다 . 여기서 size 술어 함수를 전달하는 항목의 개수로 정의된다.

규칙 :

  1. 당신의 프로그램은
    • 아이템 목록
    • 양의 정수 청크 크기
    • 술어 함수 (항목을 가져오고 true 또는 false를 리턴 함)
  2. 입력 목록을 청크로 분할하여 리턴해야합니다.
  3. 각 청크는 항목 목록입니다
  4. 전체적으로 품목은 동일한 순서로 유지되어야하며 무시하지 않아야합니다.
  5. 각 청크에 술어를 전달하는 항목 수 (마지막을 제외하고)는 입력 청크 크기와 일치해야합니다.
  6. 술어가 실패한 항목은이 크기에 포함되지 않아야합니다.
  7. 술어가 실패한 항목은
    1. 여전히 출력 청크에 포함
    2. 청크가 “full”이지만 다음 항목이 술어에 실패한 경우 가장 빠른 청크에 할당됩니다.
      • 따라서 최종 청크는 술어가 실패한 항목으로 만 구성되지 않을 수 있습니다.
  8. 모든 항목이 설명 되었기 때문에 최종 청크의 크기 는 청크 크기보다 작을 수 있습니다 .

철저하지 않은 예 :

가장 간단한 예는 술어 함수가 인 1s 및 0s 를 고려 하는 것입니다 x ==> x > 0. 이 경우 sum각 청크의 청크 크기와 일치해야합니다.

  • 항목 : [], 크기 : 2, 조건 자 : x > 0-> []또는[[]]
  • 항목 : [0, 0, 0, 0, 0, 0], 크기 : 2, 술어 : x > 0->[[0, 0, 0, 0, 0, 0]]
  • 항목 : [0, 1, 1, 0], 크기 : 2, 술어 : x > 0->[[0, 1, 1, 0]]
  • 항목 : [0, 1, 1, 0, 1, 0, 0], 크기 : 2, 술어 : x > 0->[[0, 1, 1, 0], [1, 0, 0]]
  • 항목 : [0, 1, 0, 0, 1, 0, 1, 1, 0], 크기 : 2, 술어 : x > 0->[[0, 1, 0, 0, 1, 0], [1, 1, 0]]

그리고 아기가 부모의 무릎 예제 위에 앉는 비행기 승객으로 마무리합시다 . A성인, b아기, 비행 기행은 3좌석이 넓고 어른은 항상 아기보다 먼저 나열됩니다.

  • 항목 : [A, b, A, b, A, A, A, b, A, b, A, A, b], 크기 : 3, 술어 : x => x == A->[[A, b, A, b, A], [A, A, b, A, b], [A, A, b]]


답변

젤리 , 10 바이트

vⱮTm⁵ḊœṖŒṘ

모나 딕 블랙 박스 함수를 첫 번째 선택적 인수로, 전체 목록은 두 번째 선택적 인수로, 청크 크기를 세 번째 선택적 인수로 사용하여 결과 목록 목록의 Python 표현을 인쇄하여 젤리의 암시 적 스매싱을 방지합니다. 문자가 포함 된 목록).

온라인으로 사용해보십시오! (문자 목록은 Python 인용 문자열로 형식화하여 Jelly 프로그램에 전달됨)

어떻게?

vⱮTm⁵ḊœṖŒṘ - Main Link: B, L, S
 Ɱ         - map across second argument with (i.e. for X in L):
v          -   evaluate as a monad with input (i.e. B(X))
  T        - truthy indices (e.g. [0,0,1,0,1,1,1,0,0,0,1,0,0]T -> [3,5,6,7,10])
    ⁵      - 3rd optional argument = S
   m       - modulo slice   (e.g. [3,4,7,9,12,15,16,18,19,20]m3 -> [[3,4,7],[9,12,15],[16,18,19],[20]]
     Ḋ     - dequeue        (e.g. [[3,4,7],[9,12,15],[16,18,19],[20]]Ḋ -> [[9,12,15],[16,18,19],[20]]
      œṖ   - partition right (L) at the indices in that
        ŒṘ - print Python representaion


답변

Brachylog , 37 바이트

hW&t~c.k{↰₂ˢl}ᵐ;WxĖ∧.bhᵐ↰₂ᵐ∧.t↰₂ˢl≤W∧

온라인으로 사용해보십시오!

나는 이것이 (질문의 거의 다시 언급 된) 이것이 성공적으로 종료되고 올바른 결과를 산출한다는 것을 알게되어 기뻤습니다.

술어가이 코드 아래에 술어 2로 존재한다고 가정하십시오. 목록 목록 ( “청크”)을 출력하거나 false비어있는 입력을 출력합니다.

설명:

hW&               % First input is W, the expected "weight" of each chunk
                  %  (i.e. the number of items passing predicate in each chunk)

t                 % Take the second input, the list of items
 ~c.              % Output is a partition of this list
    k{    }ᵐ      % For each partition (chunk) except the last,
      ↰₂ˢ         %   Select the items in the chunk that pass the predicate
         l        %   Get the length of that
                  % (So now we have the list of the "weights" of each chunk)
            ;Wx   % Remove the input expected weight from this list, and
               Ė  %  the result of this should be empty.
                  %  This verifies that the list of weights is either
                  %  composed of all W-values, or is empty (when input is [0 0 0] for eg.)

    ∧.bhᵐ↰₂ᵐ      % And, the first element of each chunk (except the first) should
                  %  pass the predicate. This is another way of saying:
                  %  "Items failing the predicate are allocated to the earliest chunk"

    ∧.t↰₂ˢl≤W     % And, the final chunk (which we haven't constrained so far)
                  %  should have weight ≤ the input expected weight
                  %  This disallows putting everything in the final chunk and calling it a day!

    ∧             % (no further constraints on output)


답변

Apl (Dyalog Unicode) 17 16 바이트 (SBCS)

1 바이트를 절약 해 준 Adám에게 감사합니다.

w⊆⍨⌈⎕÷⍨1⌈+\⎕¨w←⎕

온라인으로 사용해보십시오!
설명을 위해 17 바이트 솔루션을 남겨 두겠습니다.

{⍵⊆⍨⌈⍺÷⍨1⌈+\⍺⍺¨⍵}

⍺⍺¨⍵aplies 부울 벡터를 반환 목록에 술어는
+\실행중인 총 발생
1⌈선도을 대체를 0의와 1
⌈⍺÷⍨분할 최대 청크 크기와 라운드로 각 요소
⍵⊆⍨이이 파티션을 원래 벡터


답변

클린 , 96 92 바이트

f :: a -> Bool메타 합의에 따라 허용 된 명명 된 함수를 사용합니다 .

import StdEnv,StdLib
$l n|l>[]=last[[i: $t n]\\i<-inits l&t<-tails l|n>=sum[1\\e<-i|f e]]=[]

온라인으로 사용해보십시오!

확장 (설명을 표시하도록 기본 강조 표시 사용) :

$ l n // define function $ on `l` and `n`
 | l > [] // if `l` is not the empty list
  = last [ // the last element of ...
                   \\ i <- inits l // prefixes of `l`
                    & t <- tails l // matching suffixes of `l`
                    | n >= // where n is greater than or equal to
                           sum [1 \\ e <- i | f e] // the number of matching elements in the prefix
          [i: $t n] // prepend that prefix to the application of $ to the rest of the list
         ]
 = [] // if `l` is empty, return empty


답변

자바 10 207 186 159 148 바이트

a->n->{var r=new java.util.Stack();int l=a.size(),i=0,c=0,j=0;for(;i<=l;i++)if(i==l||f(a.get(i))&&++c>n&i>0){r.add(a.subList(j,j=i));c=1;}return r;}

Java는이 도전에 대한 올바른 언어가 아닙니다 (또는 물론 코드 골프 도전).

@OOBalance 덕분에 -21 바이트

온라인으로 사용해보십시오.

설명:

a->n->{                    // Method with List & int parameters & List of Lists return-type
  var r=new java.util.Stack();
                           //  Result-list, starting empty
  int l=a.size(),          //  Size of the input-List
      c=0,                 //  Count-integer, starting at 0
      j=0,                 //  Range-integer, starting at 0
  i=0;for(;i<=l;i++){      //  Loop `i` in the range [0, `l`]
    if(i==l||              //   If this is the last iteration
       f(a.get(i))         //   Or if the black-box function is true for the current item
       &&++c               //    Increase the counter by 1
        >n&                //    If the counter is now larger than the size
        &i>0){             //    and it's not the first item of the List
      a.subList(j,j=i);    //     Add a sub-List to the result from range [`j`, `i`)
                           //     And set `j` to `i` at the same time
      c=1;}                //     And reset `c` to 1
  return r;}               //  Return the List of Lists as result

블랙 박스 입력 형식 :

이 메타 답변에 따라boolean f(Object i) 허용되는 명명 된 함수 가 있다고 가정합니다 .

위의 람다뿐만 아니라 Test기본 함수를 포함 하는 추상 클래스 가 있습니다 f(i).

abstract class Test{
  boolean f(Object i){
    return true;
  }

  public java.util.function.Function<java.util.List, java.util.function.Function<Integer, java.util.List<java.util.List>>> c =
    a->n->{var r=new java.util.Stack();int l=a.size(),i=0,c=0,j=0;for(;i<=l;i++)if(i==l||f(a.get(i))&&++c>n&i>0){r.add(a.subList(j,j=i));c=1;}return r;}
  ;
}

테스트 사례의 경우이 함수를 덮어 씁니다 f. 예를 들어, 마지막 테스트 케이스는 다음과 같이 호출됩니다.

System.out.println(new Test(){
  @Override
  boolean f(Object i){
    return (char)i == 'A';
  }
}.c.apply(new java.util.ArrayList(java.util.Arrays.asList('A', 'b', 'A', 'b', 'A', 'A', 'A', 'b', 'A', 'b', 'A', 'A', 'b'))).apply(3));


답변

R , 58 바이트

function(v,g,n,a=(cumsum(Map(g,v))-1)%/%n)split(v,a*(a>0))

온라인으로 사용해보십시오!

  • @Giuseppe 덕분에 -5 바이트

답변

C (gcc) , 70 66 바이트

C는 그러한 것들에 대해 알지 못하기 때문에 하위 목록의 시작을 기록하는 구조를 사용합니다.

제안에 대한 ceilingcat에게 감사합니다.

t;f(a,s,c)l*a;int(*c)();{for(;a->v;a++)(t+=c(a->v))>s?t=++a->s:0;}

온라인으로 사용해보십시오!