Có tên cho hoạt động thiết lập/mảng này không?

Question

Với mảng đầu vào

và một chức năng 'tham gia' (a,b) => (a+b)

mã của tôi trả về mảng sau đây của mảng, chứa mỗi biến có thể thu được bằng cách áp dụng các chức năng tham gia vào cặp khác nhau của các yếu tố trong khi duy trì thứ tự:

[ 
    [a,b,c,d,e], 
    [a,b+c,d,e], 
    [a,b+c+d,e], 
    [a,b,c+d,e], 
    [a+b,c,d,e], 
    [a+b,c+d,e], 
    [a+b+c,d,e], 
    [a+b+c+d,e], 
    [a,b,c,d+e], 
    [a,b+c,d+e], 
    [a,b+c+d+e], 
    [a,b,c+d+e], 
    [a+b,c,d+e], 
    [a+b,c+d+e], 
    [a+b+c,d+e], 
    [a+b+c+d+e], 
] 

Nhìn bề ngoài, những gì tôi đang cố gắng để làm được điều này:

Mã hoạt động nhưng tôi không biết phải gọi nó là gì - và muốn sử dụng tên mà các nhà phát triển khác quen thuộc với thao tác này sẽ hiểu, nên tên như vậy tồn tại. Nó không phải là một bộ điện nhưng nó là một cái gì đó tương tự ... không hoạt động này thiết lập/mảng cụ thể có một tên?

EDIT: OK. Chúng không phải là hoán vị; hoán vị tất cả sẽ là mảng 5 phần tử theo các thứ tự khác nhau [[a,b,c,d,e], [e,d,c,b,a], [a,d,b,c,e], ...]

Chúng không phải là phân vùng, vì bất kỳ tập hợp con nào chỉ có thể chứa các phần tử liền kề của đầu vào. - nói cách khác, các phân vùng sẽ cho phép điều này:

(Điều này có lẽ bắt nguồn từ lý thuyết tập hợp tinh khiết không có khái niệm về một tập có thứ tự.)

Họ không kết hợp vì mỗi yếu tố của đầu ra sử dụng mọi thành viên của bộ đầu vào chính xác một lần.

Tôi nghĩ myArray.OrderedPartitions((a,b) => (a+b)) có lẽ là một cách ngắn gọn và phù hợp.

Answer 1

Khi mbeckish cho biết trong một nhận xét, các bộ đó là (khi một đơn đặt hàng trên bộ gốc được cố định) isomorphic để phân chia số nguyên phụ thuộc vào thứ tự, thường được gọi là compositions. Có chính xác 2 ^n-1 tác phẩm của mỗi bộ. Đối với mỗi 1 ≤ k ≤ n, có chính xác (n-1) choose (k-1) tác phẩm của n thành phần k bộ, giữ nguyên thứ tự của bộ bạn đã bắt đầu. Để hình dung nó, hãy suy nghĩ về các yếu tố của bộ bạn đặt theo thứ tự và khoảng cách giữa các yếu tố là hàng xóm theo thứ tự đó; hãy nghĩ về ví dụ của bạn là A|B|C|D|E. Bạn sẽ nhận thấy rằng có chính xác n-1 đường viền có thể. Để tạo thành phần k, bạn chỉ cần chọn k-1 các đường viền có thể, có thể hoặc không thể là cách bạn tạo bộ của mình. Tổng hợp tất cả (n-1) choose (k-1) cho k từ 1 đến n sau đó cung cấp cho chúng tôi 2 ^n-1 là số lượng tác phẩm có thể có.

Answer 2

[Chỉnh sửa lớn của người đăng khiến câu trả lời của tôi lỗi thời, đây là câu hỏi gốc được đăng:] Bách khoa toàn thư trực tuyến của chuỗi số nguyên đề cập đến một thời gian ngắn như 'các tập con khoảng thời gian'. (http://oeis.org/A000124) Tôi sẽ gắn bó với điều này, nó khá mô tả.

Answer 3

Sau khi chỉnh sửa - tất cả đều là phân vùng của một mảng (và số của chúng là 2^(n-1), vì bạn có thể thay thế bất kỳ dấu phân cách (dấu hai chấm) nào bằng joiner (+)).

Lưu ý - đây là các phân đoạn mảng, không được đặt phân vùng.

Answer 4

Đó là một cây đạo trỏ đi từ nút gốc:

Điều quan trọng cần lưu ý là bạn không khai báo theo thứ tự của bộ của bạn quan trọng, chỉ có trật tự được duy trì với mỗi bộ. Mã python để tạo "phân vùng" của bạn qua "tham gia" của bạn:

A = map(list, list('abcde')) 

def join(A): 
    B = [] 
    for x1,x2 in zip(A,A[1:]): 
     B.append((x1,x2,sorted(list(set(x1+x2))))) 
    return B 
def label(x): 
    return '+'.join(x) 

# Draw the graph with networkx 
import networkx as nx 
G = nx.DiGraph() 

while len(A)>1: 
    B = join(A) 
    for x1,x2,pair in B: 
     print label(x1), label(pair) 
     G.add_edge(label(x1),label(pair)) 
     G.add_edge(label(x2),label(pair)) 
    A = [x[2] for x in B] 

nx.write_dot(G,'test.dot') 

# Render the graph to an image 
import os 
os.system('dot -Tpng test.dot > test.png') 

Answer 5

Làm thế nào về myArray.possibleChainings() hoặc myArray.possibleLinkings()?

Ý tưởng là có vẻ như bạn đang chuỗi hoặc liên kết ít nhất hai thành phần với nhau. Tôi thấy nó cũng trực giác bởi vì bạn không thể các thành phần chuỗi hoặc liên kết với nhau mà không phải là hàng xóm.