XSD – how to allow elements in any order any number of times?

The alternative formulation of the question added in a later edit seems still to be unanswered: how to specify that among the children of an element, there must be one named child3, one named child4, and any number named child1 or child2, with no constraint on the order in which the children appear.

This is a straightforwardly definable regular language, and the content model you need is isomorphic to a regular expression defining the set of strings in which the digits ‘3’ and ‘4’ each occur exactly once, and the digits ‘1’ and ‘2’ occur any number of times. If it’s not obvious how to write this, it may help to think about what kind of finite state machine you would build to recognize such a language. It would have at least four distinct states:

• an initial state in which neither ‘3’ nor ‘4’ has been seen
• an intermediate state in which ‘3’ has been seen but not ‘4’
• an intermediate state in which ‘4’ has been seen but not ‘3’
• a final state in which both ‘3’ and ‘4’ have been seen

No matter what state the automaton is in, ‘1’ and ‘2’ may be read; they do not change the machine’s state. In the initial state, ‘3’ or ‘4’ will also be accepted; in the intermediate states, only ‘4’ or ‘3’ is accepted; in the final state, neither ‘3’ nor ‘4’ is accepted. The structure of the regular expression is easiest to understand if we first define a regex for the subset of our language in which only ‘3’ and ‘4’ occur:

(34)|(43)

To allow ‘1’ or ‘2’ to occur any number of times at a given location, we can insert (1|2)* (or [12]* if our regex language accepts that notation). Inserting this expression at all available locations, we get

(1|2)*((3(1|2)*4)|(4(1|2)*3))(1|2)*

Translating this into a content model is straightforward. The basic structure is equivalent to the regex (34)|(43):

<xsd:complexType name="paul0">
  <xsd:choice>
    <xsd:sequence>
      <xsd:element ref="child3"/>
      <xsd:element ref="child4"/>
    </xsd:sequence>
    <xsd:sequence>
      <xsd:element ref="child4"/>
      <xsd:element ref="child3"/>
    </xsd:sequence>
  </xsd:choice>
</xsd:complexType>

Inserting a zero-or-more choice of child1 and child2 is straightforward:

<xsd:complexType name="paul1">
  <xsd:sequence>
    <xsd:choice minOccurs="0" maxOccurs="unbounded">
      <xsd:element ref="child1"/>
      <xsd:element ref="child2"/>
    </xsd:choice>      
    <xsd:choice>
      <xsd:sequence>
        <xsd:element ref="child3"/>
        <xsd:choice minOccurs="0" maxOccurs="unbounded">
          <xsd:element ref="child1"/>
          <xsd:element ref="child2"/>
        </xsd:choice>      
        <xsd:element ref="child4"/>
      </xsd:sequence>
      <xsd:sequence>
        <xsd:element ref="child4"/>
        <xsd:choice minOccurs="0" maxOccurs="unbounded">
          <xsd:element ref="child1"/>
          <xsd:element ref="child2"/>
        </xsd:choice>      
        <xsd:element ref="child3"/>
      </xsd:sequence>
    </xsd:choice>
    <xsd:choice minOccurs="0" maxOccurs="unbounded">
      <xsd:element ref="child1"/>
      <xsd:element ref="child2"/>
    </xsd:choice>      
  </xsd:sequence>
</xsd:complexType>

If we want to minimize the bulk a bit, we can define a named group for the repeating choices of child1 and child2:

<xsd:group name="onetwo">
  <xsd:choice>
    <xsd:element ref="child1"/>
    <xsd:element ref="child2"/>
  </xsd:choice>   
</xsd:group>

<xsd:complexType name="paul2">
  <xsd:sequence>
    <xsd:group ref="onetwo" minOccurs="0" maxOccurs="unbounded"/>
    <xsd:choice>
      <xsd:sequence>
        <xsd:element ref="child3"/>
        <xsd:group ref="onetwo" minOccurs="0" maxOccurs="unbounded"/>
        <xsd:element ref="child4"/>
      </xsd:sequence>
      <xsd:sequence>
        <xsd:element ref="child4"/>
        <xsd:group ref="onetwo" minOccurs="0" maxOccurs="unbounded"/>
        <xsd:element ref="child3"/>
      </xsd:sequence>
    </xsd:choice>  
    <xsd:group ref="onetwo" minOccurs="0" maxOccurs="unbounded"/>
  </xsd:sequence>
</xsd:complexType>

In XSD 1.1, some of the constraints on all-groups have been lifted, so it’s possible to define this content model more concisely:

<xsd:complexType name="paul3">
  <xsd:all>
    <xsd:element ref="child1" minOccurs="0" maxOccurs="unbounded"/>
    <xsd:element ref="child2" minOccurs="0" maxOccurs="unbounded"/>
    <xsd:element ref="child3"/>
    <xsd:element ref="child4"/>      
  </xsd:all>
</xsd:complexType>

But as can be seen from the examples given earlier, these changes to all-groups do not in fact change the expressive power of the language; they only make the definition of certain kinds of languages more succinct.