寻找最小的解集（如果存在）（两个乘数） [英] Finding the smallest solution set, if one exists (two multipliers)

问题描述

注意：这是这个问题

给出一个集合 A ，该集合由0.0到1.0之间的浮点数组成，最小集 B ，这样对于 A 中的每个 a ，要么是 a == B [x] 的值，要么是一对唯一的值，其中 a == B [x] * B [y] 。

例如，给定

  $ A = [0.125，0.25，0.5，0.75，0.9] 
  

可能B的（但可能不是最小的）解决方案是

  $ B = Solve（A）
 $ print（B） 
 [0.25，0.5，0.75，0.9] 
  

这满足了最初的问题，因为 A [0] == B [0] * B [1] ， A [1] == B [1] 等，这使我们可以重新创建原始集合 A 。 B 的长度小于 A 的长度，但我想答案也较小。 / p>

我假设 B 的解决方案空间很大，即使不是无限的。如果存在解决方案，将如何找到最小的集合 B ？

---

注意：

• 我们不一定限于A中的项目。B可以由任何一组值组成，无论是


• 由于A中的项目都是0-1浮点数，因此我假设B也会是0-1浮点数。是这样吗？


• 这可能是一个约束满足问题，但我不确定如何定义？


• 由于浮点数学通常是有问题的，任何答案都应该围绕有理数来构筑算法。

解决方案

数组。对于每对元素Am，An∈A，m ＜0。 n-计算它们的比率。

检查比率是否等于A中的某个元素，既不等于Am也不等于An。

示例：

  A = {0.125，0.25，0.5，0.75，0.9} 
 
（0.125，0.25）：0.5 <---宾果
（0.125，0.5）：0.25 <---宾果
（0.125，0.75）：0.1（6）
（0.125，0.9）：0.13（8）
（0.25，0.5）：0.5 
（0.25，0.75）：0.（3）
（0.25，0.9）：0.2 （7）
（0.5，0.75）：0.（6）
（0.5，0.9）：0.（5）
（0.75，0.9）：0.8（3）
  

分子（0.125）是多余的（= 0.25 * 0.5）或（= 0.5 * 0.25）

我们可以通过引入新元素来做得更好：

另一个例子：

  A = {0.1，0.11，0.12，0.2，0.22，0.24} 
 
（0.1，0.11）：0.（90）*** 
（0.1，0.12）：0.8（3）+++ 
（0.1，0.2）：0.5< -------- 
（0.1，0.22）：0.（ 45）
（0.1，0.24）：0.41（6）
（0.11，0,12）：0.91（6）~~~ 
（0.11，0.2）：0.55 
（0.11，0.22）：0.5< -------- 
（0.11，0.24）：0.458（3）
 （0.12，0.2）：0.6 
（0.12，0.22）：0.（54）
（0.12，0.24）：0.5< -------- 
（0.2， 0.22）：0。（90）*** 
（0.2，0.24）：0.8（3）+++ 
（0.22。 0.24）：0.91（6）~~~ 
  

任意2对或更多对（a1，a2），可以用{a1，a3，...，f}替换具有共同比率f的（a3，a4），（...，...）。

因此向我们的集合中添加0.5会使{0.1，0.11，0.12}成为多余。

  B =（0.2，0.22，0.24， 0.5} 
  

我们现在（我是一般情况）面临一个优化问题，即选择其中的哪个要删除的元素以及添加哪些因素以最小化B的基数（我留给读者练习）。

请注意，没有需要引入大于1的数字。B也可以表示为{0.1，0.11，0.12，2}，但是该集合具有相同的基数。

Note: This is the two-multipliers variation of this problem

Given a set A, consisting of floats between 0.0 and 1.0, find a smallest set B such that for each a in A, there is either a value where a == B[x], or there is a pair of unique values where a == B[x] * B[y].

For example, given

$ A = [0.125, 0.25, 0.5, 0.75, 0.9]

A possible (but probably not smallest) solution for B is

$ B = solve(A)
$ print(B)
[0.25, 0.5, 0.75, 0.9]

This satisfies the initial problem, because A[0] == B[0] * B[1], A[1] == B[1], etc., which allows us to recreate the original set A. The length of B is smaller than that of A, but I’m guessing there are smaller answers as well.

I assume that the solution space for B is large, if not infinite. If a solution exists, how would a smallest set B be found?

---

Notes:

• We're not necessarily limited to the items in A. B can consist of any set of values, whether or not they exist in A.
• Since items in A are all 0-1 floats, I'm assuming that B will also be 0-1 floats. Is this the case?
• This may be a constraint satisfaction problem, but I'm not sure how it would be defined?
• Since floating point math is generally problematic, any answer should frame the algorithm around rational numbers.

解决方案

Sort the array. For each pair of elements Am, An ∈ A, m < n - calculate their ratio.

Check if the ratio is equal to some element in A, which is not equal to Am nor to An.

Example:

A = { 0.125, 0.25, 0.5, 0.75, 0.9 }

(0.125, 0.25): 0.5    <--- bingo
(0.125, 0.5 ): 0.25   <--- bingo
(0.125, 0.75): 0.1(6)
(0.125, 0.9 ): 0.13(8)
(0.25 , 0.5 ): 0.5
(0.25 , 0.75): 0.(3)
(0.25 , 0.9 ): 0.2(7)
(0.5  , 0.75): 0.(6)
(0.5  , 0.9 ): 0.(5) 
(0.75 , 0.9 ): 0.8(3)

The numerator (0.125) is redundant (= 0.25 * 0.5) or (= 0.5 * 0.25)

We can do better by introducing new elements:

Another example:

A = { 0.1, 0.11, 0.12, 0.2, 0.22, 0.24 }

(0.1 , 0.11): 0.(90)        ***
(0.1 , 0.12): 0.8(3)        +++
(0.1 , 0.2 ): 0.5     <--------
(0.1 , 0.22): 0.(45)
(0.1 , 0.24): 0.41(6)
(0.11, 0,12): 0.91(6)       ~~~
(0.11, 0.2 ): 0.55
(0.11, 0.22): 0.5     <--------
(0.11, 0.24): 0.458(3)
(0.12, 0.2 ): 0.6
(0.12, 0.22): 0.(54)
(0.12, 0.24): 0.5     <--------
(0.2 , 0.22): 0.(90)        ***
(0.2 , 0.24): 0.8(3)        +++
(0.22. 0.24): 0.91(6)       ~~~

Any 2 or more pairs (a1,a2), (a3,a4), (... , ...) with a common ratio f can be replaced with { a1, a3, ..., f }.

Hence adding 0.5 to our set makes { 0.1, 0.11, 0.12 } redundant.

B = (0.2, 0.22, 0.24, 0.5}

We are now (i the general case) left with an optimization problem of selecting which of these elements to remove and which of these factors to add in order to minimize the cardinality of B (which I leave as an exercise to the reader).

Note that there is no need to introduce numbers greater than 1. B can also be represented as { 0.1, 0.11, 0.12, 2} but this set has the same cardinality.

这篇关于寻找最小的解集（如果存在）（两个乘数）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！