최대 합계까지 지정된 숫자의 모든 시퀀스를 생성하려고 시도합니다.

Question

다음의 고유 한 고유 번호 (3,2,1) 목록이 주어지면 최대 합계로 구성된 모든 시퀀스를 생성하려고합니다.

은의이 합이 난 후 10 그런 다음 시퀀스 이하이어야한다고 가정 해 봅시다 :

3 3 3 
3 3 2 1 
3 3 2 
3 3 1 1 1 
3 3 1 1 
3 3 1 
3 3 
3 2 2 2 
3 2 2 1 1 
3 2 2 1 
3 2 2 
3 2 1 1 1 1 
3 2 1 1 1 
3 2 1 1 
3 2 1 
3 2 
3 1 1 1 1 1 1 
3 1 1 1 1 1 
3 1 1 1 1 
3 1 1 1 
3 1 1 
3 1 
3 
2 2 2 2 1 
2 2 2 2 
2 2 2 1 1 1 
2 2 2 1 1 
2 2 2 1 
2 2 2 
2 2 1 1 1 1 1 
2 2 1 1 1 1 
2 2 1 1 1 
2 2 1 1 
2 2 1 
2 2 
2 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 
2 1 1 1 1 1 
2 1 1 1 1 
2 1 1 1 
2 1 1 
2 1 
2 
1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 
1 1 1 
1 1 
1 

나는이를 생성하는 "표준"방법이 확신 해요.

나는 linq를 사용한다고 생각했지만 알아낼 수는 없습니다. 또한 스택 기반 접근 방식을 시도하고 있지만 여전히 성공하지 못했습니다.

아이디어가 있으십니까?

Answer 1

이것은 순수 LINQ가 그리 좋지 않은 재귀 적으로 작성하는 것이 가장 쉽다고 생각합니다. 따라서 이것을 보통의 재귀 함수로 구현하는 것이 가장 좋습니다. 매개 변수로는 최대 총 및 요소 ko를 추가 할 때마다에서 남아있는 양을 통과, 적절하게 총을 감소, 재귀 함수를 호출 :

IEnumerable<IEnumerable<int>> sequences(IEnumerable<int> set, int maxTotal) 
{ 
    foreach (int i in set.Where(x => x <= maxTotal)) 
    { 
     yield return new int[] { i }; 
     foreach (var s in sequences(set.Where(x => x <= i), maxTotal - i)) 
      yield return (new int[] { i }).Concat(s); 
    } 
} 

void Run() 
{ 
    foreach (var z in sequences(new int[] { 3, 2, 1 }, 10)) 
    { 
     Console.WriteLine(
      string.Join(" ", z.Select(x => x.ToString()).ToArray()) 
     ); 
    } 
} 

결과 :이 그

3 
3 3 
3 3 3 
3 3 3 1 
3 3 2 
3 3 2 2 
3 3 2 1 
3 3 2 1 1 
3 3 1 
3 3 1 1 
3 3 1 1 1 
... 
1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 

주 가장 효율적인 솔루션은 아닙니다.

Answer 2

저는 나무를 세우면 해결할 수 있다고 생각합니다. 각 노드에는 값 목록이 있습니다. 이 목록의 합계가 필요한 합계보다 작다고 가정 할 때 (이 이름을 S라고 부름),이 노드에 대해 최대 세 명의 하위 노드를 만들 수 있습니다. 하나는이 노드 목록에 1을 추가하고 나머지 하나는 2를 추가하고 하나는 3을 추가하여 자식을 구성하는 조건은 새 목록의 합이 여전히 그보다 작을 것입니다. 결국 노드를 생성 할 수 없으면 트리의 노드에 모든 시퀀스가 ​​생깁니다.

편집 : C#으로 불쌍한 내 설명은 그렇게 STH를 줄 것이다 :

첫째 :

public class Node 
{ 
    public Node() 
    { 
     Children = new List<Node>(); 
    } 

    public static int SumMax { get; set; } 

    public List<int> Values { get; set; } 

    public List<Node> Children { get; set; } 

    public void AddChild(int data) 
    { 
     if (Values.Sum() + data < SumMax) 
     { 
      Node child = new Node(); 
      child.Values = new List<int>(Values); 
      child.Values.Add(data); 
      Children.Add(child); 

      for (int = data; i < 4; i++) 
      { 
       child.AddChild(i); 
      } 
     } 
    } 

    public void FillSequences(List<List<int>> sequences) 
    { 
     if (Values.Count != 0) 
     { 
      sequences.Add(Values); 
     } 

     foreach (Node child in Children) 
     { 
      child.FillSequences(sequences); 
     } 
    } 
} 

을 다음 주 :

void Main() 
{ 
    Node.SumMax = 10; 
    Node root = new Node(); 
    root.Values = new List<int>(); 
    for (int i = 1; i < 4; i++) 
     root.AddChild(i); 

    List<List<int>> sequences = new List<List<int>>(); 
    root.FillSequences(sequences); 

    //here you've got your sequences results in "sequences" and you can do what you want 
} 

모르겠다는 표준 경우 그러나 그것은 대략 일을한다. 귀하의 필요에 맞는 것이기를 바랍니다 ...

EDIT : 동일한 순서의 생성을 피하기 위해, 우리는 트리를 "주문"할 수 있습니다 : 노드는 그 값보다 낮은 값을 가진 자식을 생성 할 수 없습니다. 따라서 AddChild 메서드에서 우리는 "data"에서 루프를 시작하고 1에서 시작하지 않습니다.

Answer 3

나는 이것이 "표준"인지 여부를 알지 못하지만 바닥에서 시작하여 일하는 것이 일반적이지 않습니다.

만드는 일 개있는 방법은 3 가지 범주로 나누어 2를 만들기 위해 2 가지 방법있다 1.

: 그 그 2부터 시작하여 1부터 시작하여, 그 3의 마지막 범주로 시작하는이 코스가 비어 있습니다.

N을 만드는 방법을 계산하려면 N-1을 1로 시작하는 방법, N-2를 2 또는 1로 시작하는 방법, N-3을 3, 2로 시작하는 방법 , 또는 1

Answer 4

가장 쉬운 방법은 (가장 효율적인 방법이 아니라면)이 방법은 숫자 집합을 가져 와서 모든 순열을 취한 다음 필터링하는 것입니다. 그 합계는 컷오프 포인트보다 높습니다.

Answer 5

partitions에 관심이있는 것처럼 보입니다. 조금 비틀어졌습니다. 이 함수는 트릭을 수행합니다. 기본적으로, 합계가 목표 합계보다 작 으면 스택에 숫자를 계속 추가 한 다음 각 단계에서 스택을 인쇄하십시오.

class Program 
{ 
    static void Main() 
    { 
     GeneratePossibilites(new int[] {3, 2, 1}, 10, 0, new List<int>()); 
    } 

    static void GeneratePossibilites(int[] array, int maxSum, int crSum, List<int> stack) 
    { 
     for (int i = 0; i < stack.Count; ++i) 
      Console.Write(array[ stack[i] ].ToString() + " "); 

     int start = 0; 
     if (stack.Count > 0) 
     { 
      start = stack[stack.Count - 1]; 
      Console.WriteLine(); 
     } 
     for (int i = start; i < array.Length; ++i) 
      if (crSum + array[i] < maxSum) 
      { 
       stack.Add(i); 
       GeneratePossibilites(array, maxSum, crSum + array[i], stack); 
       stack.RemoveAt(stack.Count - 1); 
      } 
    } 
} 

특정 형식으로 출력해야하는지 잘 모르겠지만이 답변이나 다른 답변으로 작업 할 수 있습니다.